Minimizing Rounds to Achieve Sufficient Toxicity

There are \(N\) problems numbered \(1,2,\ldots,N\). Each problem has an initial toxicity of either 0 or 1. In every round, player A can choose any contiguous block of \(K\) problems and increase the toxicity of each problem in that block by 1. However, at the start of certain rounds, player B releases a negativity attack: in a round \(w_i\), player B subtracts \(v_i\) from the toxicity of problem \(x_i\) (the toxicity is allowed to become negative). Note that if an event occurs in a round, it happens before player A makes his move in that round. Moreover, after releasing \(v_i\) points of negativity, player B must wait for at least \(r_{v_i}\) rounds before he can release negativity again. (You may assume that B’s plan is fixed and valid.)

Knowing B’s plan, player A wants to achieve a final toxicity of at least 1 on every problem in as few rounds as possible. In other words, find the minimum number of rounds \(R\) such that after simulating rounds \(1\) through \(R\), the toxicity of every problem is at least 1.

Note on the order of events in each round: In round \(r\), if a negativity event is scheduled (i.e. if there is an event with \(w_i = r\)), then the toxicity of the affected problem is reduced by \(v_i\) first, and then player A makes his move (i.e. adds 1 to all problems in his chosen contiguous block of \(K\)).

Observation: The effect of player A’s moves is independent of the order of rounds – they simply add a total of 1 per move to each covered problem. Thus, if we denote by \(\mathtt{neg}(i,R)\) the total negativity applied on problem \(i\) in all rounds \(\le R\) (i.e. summing all \(v_i\) for events with \(w_i \le R\) that occur on problem \(i\)), then the final toxicity for problem \(i\) is

[ \text{toxicity}_i = \text{initial}_i + (#\text{ of rounds in which an interval covering } i \text{ was chosen}) - \mathtt{neg}(i,R). ]

In order for \(\text{toxicity}_i \ge 1\), we must have

[ #\text{moves covering } i \ge 1 - \text{initial}_i + \mathtt{neg}(i,R). ]

This transforms the problem into the following: Given an array of deficits

[ \text{deficit}_i = \max\Big(0, 1 - \text{initial}_i + \mathtt{neg}(i,R)\Big), \quad 1 \le i \le N, ]

and given that player A makes exactly \(R\) moves (each move is a contiguous interval of length \(K\) that adds 1 to each covered problem), determine whether it is possible to choose these \(R\) intervals such that for every \(i\), the total number of moves covering \(i\) is at least \(\text{deficit}_i\).

This is a typical greedy range-add problem which can be solved by a greedy simulation (using a difference array) and binary search on \(R\) to find the minimum number of rounds needed.

inputFormat

The input consists of several lines:

• The first line contains two space‐separated integers \(N\) and \(K\).
• The second line contains \(N\) integers, each being 0 or 1, representing the initial toxicity of each problem.
• The third line contains an integer \(M\), the number of negativity events planned by player B.
• Each of the next \(M\) lines contains four space‐separated integers \(w_i\), \(x_i\), \(v_i\), and \(r_{v_i}\), meaning that at the start of round \(w_i\), player B reduces the toxicity of problem \(x_i\) by \(v_i\) and then must wait for at least \(r_{v_i}\) rounds before his next move. (It is guaranteed that the plan is valid.)

outputFormat

Output a single integer: the minimum number of rounds \(R\) after which, following the optimal strategy for player A, the toxicity of every problem is at least 1.

sample

3 2
0 0 1
1
1 1 1 1

2