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 300\,000~
~0 \le D \le 300\,000~
~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