환승 열차

뱀장어는 전철을 타는 것을 좋아한다. 지금 뱀장어는 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역까지 가는 데 걸리는 시간과 환승 횟수를 공백으로 구분해 한 줄에 출력하라.

• $N$은 1 이상 50,000 이하이다.
• $T$는 1 이상 1,000 이하인 정수이다.
• A에 정차하는 열차가 적어도 하나 있다.
• B에 정차하는 열차가 적어도 하나 있다.
• A와 B는 서로 다르다.
• $a_i$는 2 이상이다.
• $a_1 + ... + a_N$은 2 이상 100,000 이하이다.
• $s_{i,j}$는 1자 이상 10자 이하이다.
• $s_{i,j}$의 각 문자는 알파벳('A'-'Z', 'a'-'z')이다.
• $t_{i,j}$는 1 이상 1,000 이하인 정수이다.