Залізничне сполучення
Система залізничного сполучення в Токіо досить складна. Маємо часткову карту ліній і станцій, як показано на рис.1.
Рисунок 1: Приклад залізничної мережі
Припустимо, вам потрібно дістатися до станції D зі станції A. Найкоротший шлях - це A→B→D. Однак шлях з найменшою відстанню не завжди є найдешевшим. Припустимо, що лінії A-B, B-C і C-D обслуговуються однією залізничною компанією, а лінія B-D - іншою. У такому випадку проїзд по маршруту A→B→C→D може коштувати менше, ніж по A→B→D. Це тому, що вартість проїзду не завжди пропорційна відстані. Зазвичай, чим довший шлях, тим менша вартість за одиницю відстані. Якщо пасажир користується послугами кількох залізничних компаній, то вартість проїздів просто додається. Тому загальна вартість проїзду може бути вищою, ніж якби він користувався послугами однієї компанії, обравши довший шлях.
Вам надано залізничну мережу, що належить різним компаніям. Таблиця вартостей проїзду (правило, за яким обчислюється вартість проїзду залежно від відстані) для кожної компанії задається. Вам потрібно знайти шлях з найменшою вартістю між початковою та кінцевою станціями.
Вхідні дані
Вхідні дані складаються з кількох тестів, кожен з яких має наступний формат.
n m c s g x_1 y_1 d_1 c_1...x_m y_m d_m c_m p_1 ... p_c q_{1,1} ... q_{1,p1-1}r_{1,1} ... r_{1,p1}...q_{c,1} ... q_{c,pc-1} r_{c,1} ... r_{c,pc}
Вхідні дані містять лише невід'ємні цілі числа.
Перший рядок описує розмір залізничної мережі та бажану поїздку. n - кількість станцій (2 ≤ n ≤ 100). m - кількість ділянок, що з'єднують дві станції (0 ≤ m ≤ 10000). c - кількість залізничних компаній (1 ≤ c ≤ 20). s - номер початкової станції (1 ≤ s ≤ n). g - номер кінцевої станції (1 ≤ g ≤ n, g ≠ s).
Наступні m рядків описують залізничні лінії. i-а лінія (ділянка) з'єднує дві станції - x_i і y_i (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ n, x_i ≠ y_i). Рух на кожній ділянці дозволено в обох напрямках. Можуть існувати дві і більше ліній, що з'єднують одну й ту ж пару станцій. d_i (1 ≤ d_i ≤ 200) - довжина i-ї ділянки. c_i (1 ≤ c_i ≤ c) - номер залізничної компанії, яка її обслуговує.
Таблиця вартостей проїзду (співвідношення між відстанню і вартістю) для кожної залізничної компанії задається у вигляді лінійного графіка. Для компанії j кількість секцій у графіку задається значенням p_j (1 ≤ p_j ≤ 50). q_{j,k} (1 ≤ k ≤ p_j-1) дорівнює відстані, яка розділяє дві секції графіка (1 ≤ q_{j,k} ≤ 10000). r_{j,k} (1 ≤ k ≤ p_j) задає приріст вартості на одиницю відстані для відповідної секції графіка (1 ≤ r_{j,k} ≤ 100). Нехай вартість проїзду шляху довжини z становить f_j(z). Тоді вартість шляху z, що задовольняє нерівність q_j_{,k-1}+1 ≤ z ≤ q_j_{,k}, обчислюється з рекурентного співвідношення f_j(z) = f_j(z-1)+r_{j,k}. Вважайте, що q_j_{,0} і f_j(0) дорівнюють нулю, а q_j_{,pj} дорівнює нескінченності.
Наприклад, нехай p_j = 3, q_j_{,1} = 3, q_j_{,2} = 6, r_j_{,1} = 10, r_j_{,2} = 5 і r_j_{,3} = 3. У такому разі таблиця вартості проїзду має вигляд:
q_{j,k} збільшується монотонно відносно k. r_{j,k} зменшується монотонно відносно k.
Останній тест містить п'ять нулів і не обробляється.
Вихідні дані
Для кожного тесту виведіть в окремому рядку вартість найкращого шляху (шляху з найменшою вартістю). Якщо з початкової станції не можна дістатися до кінцевої, виведіть "-1". Вихідні дані не повинні містити зайвих символів, включаючи пробіли.
Якщо маршрут від початкової до кінцевої станції визначено, загальна вартість маршруту обчислюється наступним чином. Якщо дві або більше ліній однієї залізничної компанії використовуються підряд, загальна відстань цих ліній використовується для обчислення вартості цього відрізка. Загальна вартість маршруту - це сума вартостей таких "відрізків, що складаються з підряд розташованих ліній однієї компанії". Навіть якщо використовуються дві лінії однієї компанії, якщо між ними використовується лінія іншої компанії, вартості відрізків, що включають ці дві лінії, обчислюються незалежно. Жодна компанія не пропонує знижки на пересадки.