beecrowd | 1633


By Leandro Zatesko, UFFS BR Brazil

Timelimit: 1

The Federation of Awkward Cellphones and Erasers (FACE) recently signed a contract with the Federal Government to develop a low cost cellphone which is going to be distributed freely to low-income populations. Despite of being simple, many applications will be available in the device, so people will be able to enjoy all the eases that mobile platforms provide. A challenge, however, is intrigating FACE programmers: the device does not have many hardware resources, and the programmers are facing difficulties in writing the module which will manage the processes of the SBC (System for Beautiful Cellphones) operating system, developed especially for the architeture. The programmers received from the analysts the following directives, which must be strictly followed:

  1. The system runs one process at a time, and each process till the end.
  2. The system can never be idle if there are processes waiting for be attended.
  3. In order to avoid system lock, each process, when requiring its execution, must inform the system the precise duration time of its execution, in clocks. The system never allows the execution of a process going longer than expected, aborting the process if necessary. Nevertheless, if a process terminates before the informed time, the system uses the remaining clock cycles to routines of data collection and comunication with Government. Therefore, for all purposes, the execution of a process which has informed needing c clocks always lasts precisely c clocks.
  4. The system guarantees that is minimal the sum, for all processes, of the time each process waits until starting running.

Help FACE to complete SBC writing the module which is missing!


The input consists of many test cases. The first line of each test case consists of a single integer N (1 ≤ N ≤ 105), which represents the number of processes which required their execution to SBC. Each of the N following lines corresponds then to a process and consists of two integers t and c (1 ≤ t, c ≤ 103), which represent respectively the system time when the process has made its requirement and the number of clocks the execution of the process will last. Consider that the system time is counted in clocks and the counter starts in 1 in each test case. Also consider that the input ends in end-of-file (EOF).


For each test case, print the integer value which represents the sum, for all processes, of the time, in clock cycles, that each process waits until starting running. Please note that this value might not fit in 32 bits.

Sample Input Sample Output

1 10
5 15
6 10
7 5
1 10