406822: GYM102565 K Trains

AGM, the biggest music festival in the country is being held soon and people only have $$$1 \leq D \leq 10^5$$$ days to get there! There is only one way to do so: by train. There are $$$1 \leq T \leq 10^5$$$ tracks on which you may place trains with a single condition: at any time there may be only up to one train on each of the $$$T$$$ tracks. A train takes exactly $$$D$$$ days to get to the destination, regardless of the track. Formally, for a train to reach AGM in time, it should be on an open track continuously for the D days (not necessarily the same one, this will be clarified further in the statement).

But life is never that easy and because of the hot weather, some of the tracks become unusable and require some time until they can be used again. There will be $$$0 \leq q \leq 10^5$$$ updates of type $$$(a, b)$$$ which means in day $$$a$$$, the track $$$b$$$ changes its state, meaning it closes down if it was open before that, or opens up if it was closed. If a track is opened on day $$$x$$$, it can be used starting with that day. If a track is closed on day $$$x$$$, that is the last day when it can be used. If a track is closed on day $$$x$$$ and opened back up on day $$$x+1$$$, a train may not be on it continuously, meaning that if it were to continue going on that track, on day $$$x$$$ it should move to another one and on day $$$x+1$$$ it should move back.

The initial states of the tracks reflect what they are like on day $$$0$$$, meaning they can be updated starting even from day $$$1$$$.

A track may change its state twice on the same day. In that case, it is guaranteed that the first change opens the track and the second one closes it, making the track usable for that one particular day.

But you are not helpless: you have a powerful team that can move up to one train from a track to another during every single day. To perform a move, both tracks should be open during that day. This move is done instantaneously and a train that has been moved is still considered to have been continuously moving throughout that day.

Having taken all of the above in consideration, you need to say what is the maximum number of trains that can make it in time to AGM?

The first line of the input contains 2 numbers: $$$D$$$ and $$$T$$$.

The second line contains $$$T$$$ numbers $$$a_i \in \{0, 1\}$$$ describing the initial state of each track. If $$$a_i$$$ is $$$1$$$, then track $$$i$$$ is initially open.

The third line contains the number $$$q$$$.

Each of the next $$$q$$$ lines contain $$$2$$$ numbers $$$1 \leq a \leq D$$$ and $$$1 \leq b \leq T$$$, describing one of the changes.

Keep in mind each day you may move at most $$$1$$$ train from an open track to another open track.

The output should contain a single integer: the maximum number of trains that can make it in time.

7 4
1 0 1 0
4
4 1
4 3
3 2
4 4

2

At first the two trains are on track 1 and 3.

On day 3 we move one train from track 1 to track 2.

On day 4 we move one train from track 3 to track 4.