18325번 - Pod starim krovovima 스페셜 저지다국어

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.

The first line contains an integer N (1 ≤ N ≤ 1 000) from the task description.

Each of the next N lines contains two integers T_i (0 ≤ T_i ≤ 10⁹) and Z_i (1 ≤ Z_i ≤ 10⁹) 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 ≤ Z_i holds.

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.

Clarification of the second example: 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.