P13422 [COCI 2019/2020 #4] 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 \leq N \leq 1\,000$) from the task description. Each of the next $N$ lines contains two integers $T_i$ ($0 \leq T_i \leq 10^9$) and $Z_i$ ($1 \leq Z_i \leq 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 \leq 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.

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. pour one nanoliter from glass 3 into glass 5. Glasses numbered 1, 2 and 3 are now empty.