Reversible Lane

A new bridge crosses a river between two busy communities. The bridge is the bottleneck: it has $n$ lanes in total, shared by both directions, while the approach roads on each side are wider.

Traffic is not symmetric. In the morning most cars travel from the left bank to the right bank; in the evening most travel from the right bank to the left bank. The bridge is therefore configured with $n_1$ lanes permanently reserved for left-to-right traffic, $n_2$ lanes permanently reserved for right-to-left traffic, and one central reversible lane, so that $n_1 + 1 + n_2 = n$. In the morning the central lane is open for left-to-right traffic; at some moment it is switched to right-to-left traffic. Your task is to choose the best moment to switch it.

The day is split into equal time intervals, chosen so that a single lane lets exactly one car begin crossing per interval. Intervals are numbered from $1$ in the morning to $m$ in the evening. For each interval you are given how many cars arrive at the bridge on the left bank and on the right bank.

During each interval, and in each direction, three things happen in this order:

1. New cars arrive at the bridge.
2. Cars begin crossing in their direction, as many as there are lanes currently open for that direction (one car per open lane).
3. Cars that cannot start crossing wait in the queue for the next interval.

No new cars arrive after interval $m$. If cars are still waiting after interval $m$, further intervals are simulated in the same way (with no arrivals) until every car has started crossing.

Reversing the central lane is not instantaneous: it must be cleared before traffic can use it in the other direction, so it stays closed for $r$ intervals. If the switch is triggered at interval $t$ (with $1 \le t \le m$), then the open lanes are:

• before interval $t$: $n_1 + 1$ lanes left-to-right and $n_2$ lanes right-to-left;
• from interval $t$ through interval $t + r - 1$ (inclusive): $n_1$ lanes left-to-right and $n_2$ lanes right-to-left (the central lane is closed);
• from interval $t + r$ onward: $n_1$ lanes left-to-right and $n_2 + 1$ lanes right-to-left.

The total waiting time is the sum, over every interval and both directions, of the number of cars still waiting in the queue at the end of the interval (the count from step 3). Choose the interval $t$ (with $1 \le t \le m$) that minimizes the total waiting time. If several intervals achieve the minimum, report the earliest one.

The first line contains four integers $n_1$, $n_2$, $m$, and $r$, where $1 \le n_1, n_2 \le 10$, $1 \le m \le 100000$, and $1 \le r \le m$.

Each of the following $m$ lines describes one interval, in order from $1$ to $m$, with two integers: the number of cars arriving on the left bank and the number arriving on the right bank during that interval. At most $100$ cars arrive on each bank during each interval.

Output a single integer $t$ — the earliest interval at which switching the central lane minimizes the total waiting time.

The table below traces the model on the first example, using the optimal switch interval $t = 4$. For each interval it lists the lanes open in each direction, the cars that arrive (step 1), the cars that begin crossing (step 2), and the cars left waiting (step 3). The total waiting time is $20$ intervals — $10$ for left-to-right cars and $10$ for right-to-left cars. Interval $11$ is shown to make clear that nothing is waiting from that point on.