런던 지하철

런던 지하철에는 1번부터 $N$번까지 번호가 붙은 역 $N$개와 1번부터 $M$번까지 번호가 붙은 노선 $M$개가 있다. 각 노선은 정해진 순서대로 역에 정차하고, 하루 종일 양방향을 왕복한다. 한 노선에서 이웃한 두 역 사이의 거리는 양방향이 같고, 모든 역에서 양방향 열차가 1분마다 출발하므로 열차를 기다리는 시간은 들지 않는다.

노선은 정차하는 역을 순서대로 나열해서 주어지고, 각 정차역에는 노선의 출발점에서 그 역까지 걸리는 시간이 함께 붙는다. 한 노선을 타고 어떤 정차역에서 다른 정차역까지 가는 데 걸리는 시간은 두 값의 차이다.

두 노선 $L_1$과 $L_2$가 모두 $S_i$역에 정차하면 그 역에서 노선을 갈아탈 수 있고, 한 번 갈아타는 데 $S$분이 걸린다. 출발할 때 첫 노선에 타는 시간과 도착할 때 마지막 노선에서 내리는 시간은 들지 않는다.

앨리스와 밥은 런던을 여행하는 중이다. 지하철을 자주 타지만 늘 가장 빠른 길로 가고 있다는 느낌이 들지 않는다. $A$역에서 $B$역까지 가는 데 걸리는 최소 시간을 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 정수 다섯 개 $S$, $N$, $M$, $A$, $B$가 공백으로 구분되어 주어진다. 차례로 노선을 한 번 갈아타는 데 걸리는 시간, 역의 개수, 노선의 개수, 출발역, 도착역이다.

이어지는 $M$개의 줄에는 각 노선의 정보가 주어진다. 먼저 그 노선의 정차역 개수 $X$가 주어지고, 이어서 정차 순서대로 정차역 정보 $X$개가 공백으로 구분되어 주어진다. 정차역 정보는 정수 두 개로, 첫 번째 수 $Sn_i$는 역 번호이고 두 번째 수 $St_i$는 노선의 출발점에서 그 역까지 걸리는 시간이다.

• $1 \le T \le 20$
• $1 \le S \le 100$
• $2 \le N \le 100$
• $1 \le M \le 10$
• $1 \le A, B \le N$, $A \ne B$
• 모든 노선에 대해 $1 \le X \le N$
• 모든 노선에 대해 $St_0 = 0$
• 모든 노선에 대해 $St_i > St_{i-1}$
• 모든 노선에 대해 $0 \le St_i \le 1000$
• 1번부터 $N$번까지 모든 역은 적어도 한 노선에 속한다.
• 모든 역은 다른 모든 역에서 갈 수 있다.

각 테스트 케이스마다 $A$역에서 $B$역까지 가는 데 걸리는 최소 시간을 분 단위로 한 줄에 출력한다.