Setting: Legendary Zagrebian Inn called Kod Žnidaršića.

Time: The year 1936.

Plot summary: Franjo and his friends are discussing the current events in Abyssinia while enjoying a couple of drinks at the bar. His son, little Perica, is sitting at a small table in the corner of the bar. In front of Perica there are $N$ glasses conveniently numbered from $1$ to $N$. The volume (in nanoliters) of each glass is known as well as the amount of liquid that is currently inside it.

Problem: Little Perica wants to know what is the largest possible number of glasses that can be emptied by pouring the liquid between glasses. He can freely pour any integer number of nanoliters from one glass to another, as many times as he wants, as long as no liquid is spilled over.

Your task is to output the number of empty glasses along with one possible configuration of liquid in all glasses. If there are multiple configurations that yield the same number of empty glasses, output any of them. Note that it is not necessary to minimize the number of times liquid was poured between two glasses.

Input

The first line contains an integer $N$ $(1\le N\le 1000)$ from the task description.

Each of the next $N$ lines contains two integers $T_i$ $(0\le T_i\le {10}^9)$ and $Z_i$ $(1\le Z_i\le {10}^9)$ which, in that order, represent the current amount of liquid in the $i$-th glass and its volume. Both quantities are given in nanoliters and the current amount of liquid cannot be greater than the volume of the glass, i.e. $T_i\le Z_i$ holds.

Output

In the first line you should output the largest number of glasses that can be emptied by pouring the liquid between glasses.

In the second line you should output the amount of liquid in each of the glasses after Perica has performed the necessary pourings. The glasses should be ordered from glass numbered $1$ to glass numbered $N$.

Scoring

Correctly written first line is worth $4$ points, and correctly written second line is worth $1$ point for each test case.

In test cases worth a total of $20$ points, all glasses will have the same volume.

Sample Input 1

5
2 6
1 6
0 6
6 6
5 6

Sample Output 1

2
6 6 2 0 0

Sample Input 2

5
4 5
2 7
5 5
0 10
7 9

Sample Output 2

3
0 0 0 10 8

Explanation of Sample Output 2

One of the possible pouring configurations is the following:

1. pour everything from glass $1$ into glass $2$.

2. pour everything from glass $2$ into glass $4$.

3. pour four nanoliters from glass $3$ into glass $4$.

4. pour one nanoliter from glass $3$ into glass $5$.

Glasses numbered $1$, $2$ and $3$ are now empty.

Sample Input 3

8
2 6
3 4
1 1
9 10
0 10
4 5
6 8
3 9

Sample Output 3

5
0 0 0 9 10 0 0 9