うなぎは電車に乗るのが好きである. いま,うなぎは駅 A から駅 B へ電車を使って行こうとしている. うなぎは急いでいるので, 最短時間の経路を選ぶことにした. ただし,うなぎは乗り換えが苦手なので, 最短時間の経路が複数ある場合は最も乗り換え回数の少ない経路を選ぶことにした.
$N$ 本の路線がある. $i$ 本目の路線は $a_i$ 個の駅を通っている. $i$ 本目の路線の通る駅名は通る順に $s_{i,0}, ... , s_{i,a_i -1}$ であり, 駅間の所要時間は $t_{i,0}, ..., t_{i,a_i - 2}$ である. 電車は路線上を上下方向に走っており, 入力で与えられた逆順に乗ることもできる. 複数の路線の同じ駅名は同じ駅を表しており,乗り換えをすることが出来る. 乗り換えには駅や路線によらず $T$ 分かかる.
一本の路線が同じ駅を複数回通ることもある.もし同じ路線,同じ駅の,路線内で異なる位置の駅に移動したい場合は乗り換えをする必要がある. たとえば, C - D - E - F - D - G という路線を使って C から G まで行く場合, 始点から終点まで一本の電車で行くことも,D 駅で乗り換えて C - D, D - G と乗ることもできる.
うなぎが駅 A から駅 B へ行くのにかかる時間と乗り換え回数を求めよ. 電車はとても頻繁に来るので待ち時間は無視してよい.
入力は以下の形式で与えられる:
$N$ $T$
$A$ $B$
$a_1$
$s_{1,1}$ ... $s_{1,a_1}$
$t_{1,1}$ ... $t_{1,a_1 -1}$
...
$a_N$
$s_{N,1}$ ... $s_{N,a_N}$
$t_{N,1}$ ... $t_{N,a_N-1}$
うなぎが駅 A から駅 B へ行くのにかかる時間と乗り換え回数を空白で区切って1 行に出力せよ.
2 10 Warsaw Petersburg 3 Kiev Moscow Petersburg 150 120 3 Moscow Minsk Warsaw 100 150
380 1
2 10 Warsaw Petersburg 3 Kiev Moscow Petersburg 150 120 2 Minsk Warsaw 150
-1