Intercity Council for People Commute (ICPC) is in charge of operating a new bridge that connects two busy communities across the river. The bridge does not have enough throughput to accept the maximal traffic that can arrive on both sides of the bridge. The bridge has just a total of n lanes in both directions, while roads that connect to the bridge on both sides are wider.
However, the traffic on both sides of the bridge is not symmetric. In the morning more people travel from the left side of the bridge to the right side, while in the evening more people travel from the right side to the left side. So it was decided to configure a bridge with n1 lanes for left-to-right traffic, n2 lanes for right-to-left traffic, and leave one lane in the center as a reversible one (n1 +1+n2 = n). In the morning the central lane will be open for left-to-right traffic, while in the evening the central lane will be open for right-to-left traffic.
The first line of the input file contains four integer numbers n1, n2, m, and r; n1 and n2 (1 <= n1, n2 <= 10) represent the number of permanently open lanes for left-to-right and right-to-left traffic respectively; m (1 <= m <= 100 000) is the number of time intervals in a day; r (1 <= r <= m) is the number of time intervals that the central lane is closed for new traffic on reversal.
The following m lines contains traffic data on the typical day. Each line describes time interval from 1 to m with two integer numbers — the number of cars arriving at the bridge on the left and on the right. There are at most 100 arriving cars at each time interval on each side.
Write to the output file a single integer t — the earliest optimal time interval to reverse the central lane per the problem statement.
2 2 10 2 1 0 2 1 3 2 4 2 3 3 2 3 1 5 0 3 1 2 0 1
4
The tables below model the traffic for the above sample, showing at each time interval the number of lanes open in the given direction, the number of cars that arrive at each time interval (step 1 in the traffic model as given in the problem statement), the number of cars that start crossing the bridge (step 2), and the number of cars remaining in the queue (step 3). The total wait time in the queue is 20 time intervals (10 for left-to-right cars and 10 for right-to-left). Time interval 11 is explicitly shown in this table to clarify that there is no traffic on this time interval and after it in this particular sample.