Problem B
Efficient Eating

Photo by Bev Sykes, CC-BY 2.0

After your daring dash through the city in the previous problem, you’ve finally arrived at the human base. Relief! You’re totally ready for a lukewarm shower and some mediocre cafeteria food. Alas, there are many other humans in the base with you, and they all want to eat at the same time.

You get your food, and at time $t = 0$ you go to the checkout area to find $n$ lines, one for each cashier. (Capitalism is still alive and well in the post-zombie-apocalypse world, so the cafeteria charges a nominal fee for food.)

Each line $i$ contains $n_ i$ people. Each person $j$ will need $t_ j$ time to complete their transaction once they arrive at the cashier. People are also impatient, and will leave after waiting in line for $w_ j$ time (from $t = 0$) or more, if they haven’t yet reached the front of the line. People who leave don’t rejoin another line—they just give up on this meal and decide to come back to the cafeteria much later. Note that someone who reaches the front of the line at time $w_ j$ exactly will stay to complete their transaction.

Which line should you join in order to get to a cashier as quickly as possible?

Input

Input begins with one line containing a single integer $1 \leq n \leq 10$ indicating the number of checkout lines. There follow $n$ lines, each of which begins with an integer $0 \leq n_ i \leq 10^5$ indicating the number of people in the line. If $n_ i > 0$, it is followed by one space and then $2n_ i$ space-separated integers. Every adjacent pair of these integers corresponds to one person in the line, starting with the person at the front of the line and continuing in order. Each pair of integers consists of $1 \leq t_ j \leq 20$, the transaction time of the person, and $0 \leq w_ j \leq 10^6$, the time at which the person will leave the line if they haven’t yet made it to the front. A value of $w_ j = 0$ indicates the person is willing to wait indefinitely.

Output

Output a single line containing one integer: the index of the line that will get you to a cashier in the minimum possible time. Indices start from $0$. If more than one line gives you the minimum possible time, output the lowest index.

3
1 15 2
2 4 7 8 17
2 10 1 4 18

1

3
1 15 2
2 4 7 8 17
2 10 1 4 8

2