Dəmir Yolu Əlaqəsi
Tokiodakı dəmir yolu sistemi olduqca mürəkkəbdir. Şəkil 1-də xətlərin və stansiyaların qismən xəritəsi göstərilmişdir.
Şəkil 1: Nümunə dəmir yolu şəbəkəsi
Tutaq ki, siz A stansiyasından D stansiyasına getməlisiniz. Ən qısa məsafəli yol A→B→D-dir. Lakin ən qısa məsafəli yol həmişə ən ucuz yol olmur. Məsələn, A-B, B-C və C-D xətləri bir dəmir yolu şirkəti tərəfindən, B-D xətti isə başqa bir şirkət tərəfindən idarə olunursa, A→B→C→D marşrutu A→B→D marşrutundan daha ucuz ola bilər. Bunun səbəbi səyahət xərclərinin məsafə ilə mütənasib olmamasıdır. Adətən, yol nə qədər uzun olarsa, məsafə vahidinə görə səyahət xərci bir o qədər azalır. Əgər sərnişin bir neçə dəmir yolu şirkətinin xidmətlərindən istifadə edirsə, səyahət xərcləri sadəcə toplanır. Buna görə də, bir şirkətin xidmətlərindən istifadə edərək daha uzun bir yol seçmək daha sərfəli ola bilər.
Sizə müxtəlif şirkətlərə məxsus olan dəmir yolu şəbəkəsi təqdim olunur. Hər bir şirkət üçün səyahət xərcləri cədvəli (məsafəyə görə səyahət xərci necə hesablanır) verilir. Başlanğıc və son stansiyalar arasında ən az xərcli yolu tapmalısınız.
Giriş verilənləri
Bir neçə testdən ibarətdir, hər biri aşağıdakı formatda verilmişdir.
n m c s g
x_1 y_1 d_1 c_1
...
x_m y_m d_m c_m
p_1
q_{1,1} ... q_{1,p1-1}
r_{1,1} ... r_{1,p1}
...
p_c
q_{c,1} ... q_{c,pc-1}
r_{c,1} ... r_{c,pc}
Giriş məlumatları yalnız qeyri-mənfi tam ədədlərdən ibarətdir.
Birinci sətir dəmir yolu şəbəkəsinin ölçüsünü və arzu olunan səyahəti təsvir edir. n - stansiyaların sayı (2 ≤ n ≤100). m - iki stansiyanı birləşdirən hissələrin sayı (0 ≤ m ≤ 10000). c - dəmir yolu şirkətlərinin sayı (1≤ c ≤ 20). s - başlanğıc stansiyanın nömrəsi (1 ≤ s ≤ n). g - son stansiyanın nömrəsi (1≤ g ≤ n, g ≠ s).
Növbəti m sətir dəmir yolu xətlərini təsvir edir. i-ci xətt (hissə) iki stansiyanı birləşdirir - x_i və y_i (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ n, x_i ≠ y_i). Hər bir hissədə hər iki istiqamətdə hərəkətə icazə verilir. Eyni cüt stansiyanı birləşdirən iki və ya daha çox xətt mövcud ola bilər. d_i (1 ≤ d_i ≤ 200) - i-ci hissənin uzunluğu. c_i (1 ≤ c_i ≤ c) - onu idarə edən dəmir yolu şirkətinin nömrəsi.
Hər bir dəmir yolu şirkəti üçün səyahət xərcləri cədvəli xətti qrafik şəklində verilir. Şirkət j üçün qrafikdəki hissələrin sayı p_j (1 ≤ p_j ≤ 50) ilə verilir. q_{j,k} (1 ≤ k ≤ p_j-1) qrafikdəki iki hissəni ayıran məsafəyə bərabərdir (1 ≤ q_{j,k} ≤ 10000). r_{j,k} (1 ≤ k ≤ p_j) müvafiq qrafik hissəsi üçün məsafə vahidinə görə xərclərin artımını təyin edir (1 ≤ r_{j,k} ≤ 100). Tutaq ki, z uzunluğundakı yolun səyahət xərci f_j(z) təşkil edir. O zaman q_j_{,k-1}+1 ≤ z ≤ q_j_{,k} bərabərsizliyini ödəyən z uzunluğundakı yolun xərci rekursiv olaraq f_j(z) = f_j(z-1)+r_{j,k} ilə hesablanır. q_j_{,0} və f_j(0) sıfıra, q_j_{,pj} isə sonsuzluğa bərabərdir.
Məsələn, tutaq ki, p_j = 3, q_j_{,1} = 3, q_j_{,2} = 6, r_j_{,1} = 10, r_j_{,2} = 5 və r_j_{,3} = 3. Bu halda səyahət xərcləri cədvəli belə görünür:
q_{j,k} k-yə görə monoton şəkildə artır. r_{j,k} k-yə görə monoton şəkildə azalır.
Son test beş sıfırdan ibarətdir və işlənmir.
Çıxış verilənləri
Hər bir test üçün ən yaxşı yolun (ən az xərcli yolun) xərclərini ayrıca sətirdə çap edin. Əgər başlanğıc stansiyadan son stansiyaya getmək mümkün deyilsə, "-1" çap edin. Çıxış məlumatları artıq simvollar, o cümlədən boşluqlar içerməməlidir.
Başlanğıcdan məqsədə qədər bir marşrut müəyyən edildikdən sonra, marşrutun ümumi xərci aşağıdakı kimi hesablanır. Əgər eyni dəmir yolu şirkətinin iki və ya daha çox xətti ardıcıl istifadə olunursa, bu xətlərin ümumi məsafəsi bu hissənin xərclərini hesablamaq üçün istifadə olunur. Marşrutun ümumi xərci belə "eyni şirkətin ardıcıl xətlərindən ibarət hissələrin" xərclərinin cəmidir. Hətta eyni şirkətin iki xəttindən istifadə edilsə də, bu iki xətt arasında başqa bir şirkətin xətti istifadə olunarsa, bu hissələrin xərcləri müstəqil olaraq hesablanır. Heç bir şirkət tranzit endirimi təklif etmir.