010 - 電車乗り換え

時間制限 5 秒 / メモリ制限 256 MB / 得点 18 / x 0 /


TLE
5sec
MLE
256MB
得点
18

もんだいー

うなぎは電車に乗るのが好きである。いま,うなぎは駅Aから駅Bへ電車を使って行こうとしている。
うなぎは急いでいるので,最短時間の経路を選ぶことにした。ただし,うなぎは乗り換えが苦手なので,最短時間の経路が複数ある場合は最も乗り換え回数の少ない経路を選ぶことにした。

N本の路線がある。i本目の路線はai個の駅を通っている。
i本目の路線の通る駅名は通る順にsi,0,...,si,ai-2であり、駅間の所要時間はti,0,...ti,ai-2である。電車は路線上を上下方向に走っており,入力で与えられた逆順に乗ることもできる。複数の路線の同じ駅名は同じ駅を表しており,乗り換えをすることが出来る。乗り換えには駅や路線によらずT分かかる。一本の路線が同じ駅を複数回通ることもある。もし同じ路線,同じ駅の,路線内で異なる位置の駅に移動したい場合は乗り換えをする必要がある。

たとえば, C-D-E-F-D-Gという路線を使ってCからGまで行く場合,始点から終点まで一本の電車で行くことも,D駅で乗り換えてC-D,D-Gと乗ることもできる。うなぎが駅Aから駅Bへ行くのにかかる時間と乗り換え回数を求めよ。 電車はとても頻繁に来るので待ち時間は無視してよい。

入力

N T
A B
a1
s1,1 ... s1,a1
t1,1 ... t1,a1-1
.
.
.
aN
sN,1 ... sN,aN
tN,1 ... tN,aN-1

出力

うなぎが駅Aから駅Bへ行くのにかかる時間と乗り換え回数を空白で区切って1行に出力せよ。

制約

N will be between 1 and 50,000, inclusive.
T will be an integer between 1 and 1,000, inclusive.
At least one train stops at A.
At least one train stops at B.
A and B will be distinct.
ai will be bigger than or equal to 2.
a1+...+aN will e between 2 and 100,000, inclusive.
si,j will contain between 1 and 10 characters, inclusive.
Each character in si,j will be a letter ('A'-'Z', 'a'-'z').
ti,j will be an integer between 1 and 1,000, inclusive.


入出力例

入力例1

2 10
Warsaw Petersburg
3
Kiev Moscow Petersburg
150 120
3
Moscow Minsk Warsaw
100 150

出力例1

380 1

入力例2

2 10
Warsaw Petersburg
3
Kiev Moscow Petersburg
150 120
2
Minsk Warsaw
150

出力例2

-1