시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 39 25 6 42.857%

문제

초라기는 한국의 비밀 국방 기지 원타곤을 습격하는 임무를 받은 특급 요원이다. 원타곤은 도넛 형태이며, 아래와 같이 2N개의 구역으로 나뉜다. (그림의 숫자는 각 구역의 번호이다.)

초라기는 특수 소대들을 출동시켜 모든 구역을 점령하고 적들을 포로로 사로잡는 데 성공했다. 특수 소대는 아래 조건에 따라 원타곤의 각 구역에 배치되어 포로들을 관리한다.

  1. 한 특수 소대는 구역 하나 또는 서로 인접한 두 구역에 배치할 수 있다. (같은 경계를 공유하고 있으면 인접하다고 한다. 위 그림에서 구역 1은 구역 2, 구역 N, 구역 N+1과 서로 인접한 상태이다.)
  2. 한 특수 소대가 관리하는 포로의 수는 W보다 작거나 같아야 한다.

각 구역에 포로들이 몇 명씩 있는지는 초라기가 모두 파악하고 있다. 그런데 다른 곳으로 이송되는 포로도 있고 증원군으로 왔다 잡혀서 새로 포로가 되는 적들도 있다보니 계속 각 구역의 포로 수가 바뀌어 초라기가 더 이상 관리 불가능한 수준에 이르고 말았다. 초라기가 가진 특수 소대는 많지 않기 때문에, 초라기는 특수 소대를 최소한으로 배치하고 싶다. Q번에 걸쳐 한 번에 한 구역의 포로 수가 바뀔 때, 초라기를 위해 필요한 특수 소대 수의 최솟값을 실시간으로 구해주자.

입력

첫째 줄에는 정수 N, Q, W가 공백으로 구분되어 주어진다. (2 ≤ ≤ 250 000, 1 ≤ Q ≤ 250 000, 1 ≤ W ≤ 100 000)

둘째 줄에는 점령 직후 구역 1 – N에 존재하는 포로의 수가 공백으로 구분되어 주어진다.

셋째 줄에는 점령 직후 구역 N+1 – 2N에 존재하는 포로의 수가 공백으로 구분되어 주어진다. 각 구역의 포로의 수는 0보다 크거나 같고 W보다 작거나 같다.

그 다음 Q줄에는 각 줄마다 정수 a, b가 공백으로 구분되어 주어진다. (1 ≤ a ≤ 2N, 0 ≤ b W) 이는 구역 a에 존재하는 포로의 수가 b명으로 변경되었다는 것을 의미한다.

출력

첫째 줄에는 점령 직후 필요한 특수 소대 수의 최솟값을 출력한다.

그 다음 Q줄에는 각 줄마다 포로 수가 변경되고 나서 필요한 특수 소대 수의 최솟값을 출력한다.

예제 입력 1

3 6 1
0 0 0
0 0 0
1 1
2 1
3 1
4 1
5 1
6 1

예제 출력 1

3
3
3
3
4
5
6

예제 입력 2

8 10 100
70 60 55 43 57 60 44 50
58 40 47 90 45 52 80 40
5 30
9 0
14 48
16 91
7 15
1 27
3 6
11 53
4 65
10 89

예제 출력 2

11
10
10
10
10
10
9
9
9
9
10

출처