TROLLEYBUS ROUTES

Mykola arrived at the regional informatics olympiad but realized he was running late as soon as he left the station. To reach the olympiad venue as quickly as possible, he decided to take advantage of the free trolleybus rides available to olympiad participants in the city.

The city has N stops and is served by K trolleybus routes.

The routes and the travel time between each pair of stops are known.

Each trolleybus route has distinct starting and ending stops, meaning the routes are not circular.

At time zero (t = 0), trolleybuses depart from all terminal stops. On each route, two trolleybuses set off from the terminal stops towards each other. When a trolleybus arrives at a terminal stop, another trolleybus immediately departs in the opposite direction.

Mykola is currently at stop A and needs to reach stop B.

He can transfer between trolleybuses at stops, but he might need to wait for the next one. The waiting time for a trolleybus, as well as the time for disembarking and boarding, is considered to be 0.

Determine the number of minutes it will take Mykola to reach the olympiad venue, or output -1 if it is impossible for him to reach the destination.

Input

The first line contains the numbers N and K (3 ≤ N ≤ 100, 1 ≤ K ≤ 1000).The second line contains the stop numbers A and B (1 ≤ A, B ≤ N).The next K lines describe each route:The first number M[i] in each line indicates the number of stops on the trolleybus route; following this are M[i] * 2 - 1 numbers that describe the stop numbers of the route and the travel time between them (stop number; travel time to the next stop; next stop number; travel time to the next stop; next stop number, etc.).All numbers are integers.

Output

The time it will take Mykola to reach the olympiad venue, or -1 if Mykola cannot reach the destination.

Examples

Note

Mykola starts at stop №1 and needs to get to stop №8.

There are three trolleybus routes:

1-5-7-8 (and return 8-7-5-1)

2-5-6-8 (and return 8-6-5-2)

3-8-7-6-4 (and return 4-6-7-8-3)

Mykola takes the following steps:

● At time 0 (t = 0), he boards a trolleybus at stop №1 and gets off at stop №5 after 2 minutes (t = 2);

● He waits a minute and boards a trolleybus arriving from stop №2 (t = 3);

● He travels one stop and gets off at stop №6 (t = 4);

● He waits two minutes until a trolleybus arrives from stop №4 (t = 6);

● He boards and travels to stop №8 (t = 10).