Political Instability

View as PDF

Points: 17
Time limit: 5.0s
Memory limit: 256M

Author:
Problem type

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 political parties in Collea, which are conveniently numbered from to , and current polls show that if the election was to be held today, the th political party would earn 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 following days, some political parties had their expected number of votes changed. Specifically, on the th day, the th party's expected number of votes changed to . Help Collea find the minimum number of parties required such that they form a majority coalition for each day.

Constraints

It is guaranteed that the total number of votes will always be positive.

Input Specifications

The first line contains two integers, and .
The second line contains integers,
lines follow, the th of which contains the integers and

Output Specifications

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

Sample Input

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

Sample Output

2
2
3
2