Hide

Problem G
Coffee Date

Erika and Leah have not had a cup of coffee together for too long, and want to meet up today. Both of them like all the coffee shops in the city, so they decide to meet up at the coffee shop where they can see each other as soon as possible.

As they both live right by bus stops, they can take any of the buses that go by their home. They can also switch to another bus at a bus stop and can do so instantly, or wait until some other bus arrives.

The buses in the city are always on time, and all the routes have a new bus starting at some interval $C_ i$ all day. By pure chance, all the routes have a new bus starting right now.

As there is a coffee shop by every bus stop, Leah wants to know the earliest time they can see each other.

Input

The first line contains four integers $B$, $N$, $B_ e$, $B_ l$: The number of bus stops, the number of bus routes, the bus stop by Erika’s apartment, and the bus stop by Leah’s apartment. Then follow $3N$ lines, three lines in a row for each bus stop.

Each bus route starts with a line with the integers $C_ i$ and $S_ i$: The interval before a new bus starts, and the number of bus stops this route stops at, respectively. Then follows a line with $S_ i$ integers $s_{i,j}$, the number of each bus stop in order: $s_{i,0}$ is the start stop, $s_{i,1}$ is the next stop, and so on. After that comes a line with $S_ i - 1$ integers $t_{i,j}$, the time it takes to go from bus stop $s_{i,j}$ to stop $s_{i,j+1}$.

Output

Output the earliest time Erika and Leah will see each other, assuming they both wait at the bus station right now. If there is no way they can meet, output ‘NO COFFEE FOR YOU’.

Limits

  • $0 \leq B_ e, B_ l, s_{i,j} < B \leq 1\, 000$

  • $0 \leq N \leq 100$

  • $1 \leq C_ i, t_{ij} < 1\, 000$

  • $2 \leq S_ i \leq B$

  • A bus only arrives at a bus stop once

Sample Input 1 Sample Output 1
9 4 0 7
1 4
3 7 6 5
9 7 2
2 4
8 5 4 3
4 2 2
7 4
0 1 6 3
7 8 6
2 3
1 2 3
2 2
14

Please log in to submit a solution to this problem

Log in