After the end of the war, Collea was left in a state of political turmoil. Having been forced to install a democratic government, and with the rise of extremist attitudes throughout the country, the current Collean government is anxious about the coming national election. There are $N$ political parties in Collea, which are conveniently numbered from $1$ to $N$, and current polls show that if the election was to be held today, the $i$th political party would earn $v_i$ votes. In order for a new government to form, some of the political parties must form a majority coalition where the sum of the votes of the parties in the coalition must be strictly greater than half of the total votes. In the $D$ following days, some political parties had their expected number of votes changed. Specifically, on the $i$th day, the $a_i$th party's expected number of votes changed to $b_i$. Help Collea find the minimum number of parties required such that they form a majority coalition for each day.

Constraints

$1\le N\le 300000$
$0\le D\le 300000$
$0\le b_i,v_i\le {10}^9$
$1\le a_i\le N$
It is guaranteed that the total number of votes will always be positive.

Subtask 1 [10%]

$1\le N,D\le 2000$

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line contains two integers, $N$ and $D$.
The second line contains $N$ integers, $v_1,v_2,\dots ,v_N$.
$D$ lines follow, the $i$th of which contains the integers $a_i$ and $b_i$.

Output Specification

On the first line, output one integer, the minimum possible number of parties in a majority coalition before the $D$ days.
Output $D$ more lines, the $i$th of which containing one integer, the minimum possible number of parties in a majority coalition after the $i$th day.

Sample Input

5 3
3 1 5 2 2
2 3
5 3
4 5

Sample Output

2
2
3
2