가변 차로

두 지역을 잇는 강 위에 새 다리가 놓였다. 다리가 병목이다. 다리에는 양방향이 함께 쓰는 차로가 모두 $n$개뿐이지만, 다리로 이어지는 양쪽 도로는 그보다 넓기 때문이다.

교통량은 대칭이 아니다. 아침에는 대부분의 차량이 왼쪽 강변에서 오른쪽 강변으로 이동하고, 저녁에는 대부분 오른쪽에서 왼쪽으로 이동한다. 그래서 다리는 왼쪽→오른쪽 전용 차로 $n_1$개, 오른쪽→왼쪽 전용 차로 $n_2$개, 그리고 방향을 바꿀 수 있는 가변 중앙 차로 $1$개로 구성되며 $n_1 + 1 + n_2 = n$을 만족한다. 아침에는 중앙 차로가 왼쪽→오른쪽 방향으로 열려 있고, 어느 시점에 오른쪽→왼쪽 방향으로 전환된다. 이 전환을 언제 하는 것이 가장 좋은지 정하는 것이 목표다.

하루는 길이가 같은 시간 구간으로 나뉜다. 차로 하나가 한 구간에 정확히 차량 한 대를 건너기 시작하게 할 수 있도록 구간 길이가 정해져 있다. 구간은 아침의 $1$번부터 저녁의 $m$번까지 번호가 매겨진다. 각 구간마다 왼쪽 강변과 오른쪽 강변에 도착하는 차량 수가 주어진다.

각 구간에서 양쪽 방향 모두 다음 순서로 진행된다.

1. 새 차량이 다리에 도착한다.
2. 해당 방향으로 현재 열려 있는 차로 수만큼(차로 하나당 한 대씩) 차량이 건너기 시작한다.
3. 건너기 시작하지 못한 차량은 다음 구간까지 대기열에서 기다린다.

$m$번 구간 이후로는 새 차량이 도착하지 않는다. $m$번 구간이 끝난 뒤에도 기다리는 차량이 있으면, 모든 차량이 건너기 시작할 때까지 같은 방식으로(도착 차량 없이) 구간을 계속 진행한다.

중앙 차로의 방향 전환은 즉시 이루어지지 않는다. 반대 방향 차량이 쓰기 전에 차로를 비워야 하므로, 전환 동안 $r$개 구간만큼 닫혀 있다. 전환을 $t$번 구간($1 \le t \le m$)에 시작하면 열려 있는 차로는 다음과 같다.

• $t$번 구간 이전: 왼쪽→오른쪽 $n_1 + 1$개, 오른쪽→왼쪽 $n_2$개;
• $t$번 구간부터 $t + r - 1$번 구간까지(양 끝 포함): 왼쪽→오른쪽 $n_1$개, 오른쪽→왼쪽 $n_2$개(중앙 차로가 닫힘);
• $t + r$번 구간 이후: 왼쪽→오른쪽 $n_1$개, 오른쪽→왼쪽 $n_2 + 1$개.

총 대기 시간은 모든 구간과 양쪽 방향에 대해, 각 구간이 끝난 시점에 대기열에 남아 있는 차량 수($3$단계의 값)를 모두 더한 값이다. 총 대기 시간을 최소로 만드는 구간 $t$($1 \le t \le m$)를 구하라. 최솟값을 만드는 구간이 여러 개면 가장 이른 것을 출력한다.

첫 줄에 네 정수 $n_1$, $n_2$, $m$, $r$가 주어진다. $1 \le n_1, n_2 \le 10$, $1 \le m \le 100000$, $1 \le r \le m$이다.

다음 $m$개의 줄에는 $1$번부터 $m$번까지 각 구간의 정보가 순서대로 주어진다. 각 줄에는 두 정수가 있으며, 그 구간에 왼쪽 강변에 도착하는 차량 수와 오른쪽 강변에 도착하는 차량 수를 나타낸다. 각 구간에 각 강변으로 도착하는 차량은 최대 $100$대다.

총 대기 시간을 최소로 만드는 가장 이른 전환 구간 $t$를 정수 하나로 출력한다.

아래 표는 첫 번째 예제에 대해 최적 전환 구간 $t = 4$를 사용했을 때의 모델을 보여 준다. 각 구간마다 방향별로 열린 차로 수, 도착한 차량($1$단계), 건너기 시작한 차량($2$단계), 대기열에 남은 차량($3$단계)을 나타낸다. 총 대기 시간은 $20$구간이다(왼쪽→오른쪽 $10$, 오른쪽→왼쪽 $10$). $11$번 구간은 그 이후로 대기 중인 차량이 없음을 분명히 하기 위해 함께 표시했다.