London Underground

The London Underground has $N$ stations, numbered 1 to $N$, and $M$ lines, numbered 1 to $M$. Each line stops at a fixed sequence of stations and runs back and forth all day. Two consecutive stations on a line are the same distance apart in both directions, and a train leaves every station in both directions every minute, so waiting for a train takes no time.

A line is given as its stops in order, and each stop carries the number of minutes from the start of the line to that station. Riding one line from one of its stops to another takes the difference between those two numbers.

You can change from line $L_1$ to line $L_2$ at station $S_i$ when both lines stop at $S_i$, and one change takes $S$ minutes. Boarding the first line at the start of the trip and leaving the last line at the end take no time.

Alice and Bob are visiting London. They ride the underground a lot, and they keep feeling that they are not always taking the fastest route. Find the shortest travel time from station $A$ to station $B$.

The first line has one integer $T$, the number of test cases.

Each test case begins with a line of five integers $S$, $N$, $M$, $A$, $B$, separated by spaces. They give the number of minutes one line change takes, the number of stations, the number of lines, the start station, and the end station.

The next $M$ lines describe the subway lines. Each of those lines begins with an integer $X$, the number of stops on that subway line, followed by $X$ stop specifications separated by spaces, in the order the stops appear along the line. A stop specification is two integers, where the first number $Sn_i$ is the station number and the second number $St_i$ is the number of minutes from the start of the line to that station.

• $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$ and $A \ne B$
• $1 \le X \le N$ for every line
• $St_0 = 0$ for every line
• $St_i > St_{i-1}$ for every line
• $0 \le St_i \le 1000$ for every line
• Every station from 1 to $N$ is on at least one line.
• Every station is reachable from every other station.

For each test case, print on its own line the smallest number of minutes needed to travel from station $A$ to station $B$.