This page is still under construction.

Parts of this page are still being built. What you see may change.

Raider Choragi and Queries (Normal)

Time limit5sMemory limit512 MB

Summary
A donut-shaped ring of 2N zones holds prisoner counts that change over Q updates; after each change, print the minimum number of squads, each covering one zone or two adjacent zones with total at most W.
Level

Hard8 of 10

Topics
Dynamic programming, Segment tree, Matrix, Greedy
Solved
No attempts yet

Problem

Choragi is an elite agent tasked with raiding Wontagon, a secret national defense base of Korea. Wontagon has the shape of a donut and is divided into 2N zones as shown below. (The numbers in the figure are the zone numbers.)

Choragi deployed special squads, captured every zone, and took the enemies prisoner. The special squads are placed in the zones of Wontagon under the following conditions to manage the prisoners.

  1. A special squad can be placed in one zone or in two mutually adjacent zones. (Two zones are adjacent if they share a boundary. In the figure above, zone 1 is adjacent to zone 2, zone N, and zone N+1.)
  2. The number of prisoners managed by one special squad must be less than or equal to W.

Choragi knows how many prisoners are in each zone. However, some prisoners are transferred elsewhere and some enemies come as reinforcements, get captured, and become new prisoners, so the prisoner counts keep changing and have reached a level Choragi can no longer manage. Since Choragi does not have many special squads, Choragi wants to place as few special squads as possible. Over Q updates, where the prisoner count of one zone changes per update, find for Choragi the minimum number of special squads needed in real time.

Input

The first line contains the integers N, Q, and W, separated by spaces. (2 ≤ N ≤ 250 000, 1 ≤ Q ≤ 250 000, 1 ≤ W ≤ 100 000)

The second line contains the prisoner counts in zones 1 to N immediately after the capture, separated by spaces.

The third line contains the prisoner counts in zones N+1 to 2N immediately after the capture, separated by spaces. Each zone's prisoner count is greater than or equal to 0 and less than or equal to W.

Each of the next Q lines contains the integers a and b, separated by spaces. (1 ≤ a ≤ 2N, 0 ≤ b ≤ W) This means the number of prisoners in zone a has changed to b.

Output

The first line prints the minimum number of special squads needed immediately after the capture.

Each of the next Q lines prints, after the corresponding prisoner count change, the minimum number of special squads needed.

Examples2

  1. Example 1

    Input
    3 6 1
0 0 0
0 0 0
1 1
2 1
3 1
4 1
5 1
6 1
    Expected output
    3
3
3
3
4
5
6

  2. Example 2

    Input
    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
    Expected output
    11
10
10
10
10
10
9
9
9
9
10