0161 - 鉄道乗り継ぎ

東京の鉄道ネットワークは非常に複雑である． たとえば，図D-1のような路線図が含まれている．

図D-1: 路線図の例

この路線図の上で，A駅からD駅に行きたいとする． 最短距離の経路を選ぶなら，A→B→Dと行けばよいことは明らかである． しかし，最短距離の経路が必ず最小コストの経路になるとは限らない． 図で，A-B，B-C，C-Dが同じ鉄道会社の線で，B-Dだけ別の会社の線だったとする． この場合，A→B→C→Dの経路の方がA→B→Dの経路より安いことがありうる． その要因の一つは，運賃が距離に比例していないことである． 距離が長いほど，単位距離当たりの運賃は安くなるように設定されていることが多い． 複数の会社の線を乗り継ぐと，それぞれの会社の運賃を単純に合計するので， 単一の会社の線だけを使った経路に比べて，距離は短くとも， 運賃は割高になってしまうことがあるのだ．

この問題では，複数の鉄道会社からなる路線図が与えられる． また，それぞれの会社の運賃表（距離から運賃を計算するルール）が与えられる． 出発地と目的地が与えられたとき，最も安い運賃の経路を求めるプログラムを書くことがあなたの仕事である．

入力は複数のデータセットから構成される． 各データセットの形式は次に示すとおりである．

n m c s g
x₁ y₁ d₁ c₁
...
x_m y_m d_m c_m
p₁ ... 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

データセットの中の入力項目は，すべて非負の整数である． 行中の入力項目の区切りは空白1個である．

最初の行は，鉄道ネットワークの大きさと実現したい旅行を規定する． n は駅の数である(2 ≤ n ≤ 100)． m は駅と駅をつなぐ路線の数である(0 ≤ m ≤ 10000)． c は鉄道会社の数である(1 ≤ c ≤ 20)． s は出発地の駅番号である(1 ≤ s ≤ n)． g は目的地の駅番号である(1 ≤ g ≤ n, g ≠ s)．

続いて，m 本の路線のデータが順次与えられる． それぞれの行は，二つの駅x_i とy_i を結ぶ路線の記述である(1 ≤ x_i ≤ n, 1 ≤ y_i ≤ n, x_i ≠ y_i)． 各路線は，どちらの方向の移動にも使える． 同じ二つの駅を結ぶ路線が2本以上存在することもあり得る． d_i は，その路線の長さ（移動距離）である(1 ≤ d_i ≤ 200)． c_i は，その路線を運営する鉄道会社の番号である(1 ≤ c_i ≤ c)．

各鉄道会社の運賃表（距離と運賃の関係）は折れ線グラフで与えられる． 鉄道会社j 番に対して， 折れ線の区間の数（折れ目の数プラス 1）が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 当たりの運賃の増分を与える (1 ≤ r_j,k ≤ 100)． より詳しく言えば，距離z のときの運賃を f_j (z) と表すと， q_j,k-1+1 ≤ z ≤ q_j,k を満たす距離z に対して 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" と出力すること． 出力行の中に，結果を表す文字以外のもの（たとえば空白）が含まれていてはならない．

出発地から目的地までの経路を定めたときの運賃の計算ルールは次のとおりとする． 同じ会社の複数の路線を連続して経由する場合は，これらの路線の合計距離に基づいて運賃を決める． 全体の運賃は，こうして決めた同一会社連続区間の運賃の総和である． 同じ会社の路線を複数利用していても，間にほかの会社の路線がはさまっている場合は，前後の区間の運賃を独立に計算する． 乗り継ぎ割引のような制度は存在しない．

4 4 2 1 4
1 2 2 1
2 3 2 1
3 4 5 1
2 4 4 2
3 1
3 6
10 5 3

10
2 0 1 1 2
1

1
4 5 2 4 1
4 3 10 1
3 2 2 1
3 2 1 2
3 2 5 2
2 1 10 1
3 3
20 30
3 2 1
5 10
3 2 1
5 5 2 1 5
1 2 10 2
1 3 20 2
2 4 20 1
3 4 10 1
4 5 20 1
2 2
20
4 1
20
3 1
0 0 0 0 0

54
-1
63
130