A1478.[COCI-2012_2013-contest2]#6 POPUST

Mirko is hungry as a bear, scratch that, programmer and has stumbled upon a local restaurant. The restaurant offers N meals and has an interesting pricing policy: each meal i has two assigned prices, Ai and Bi . Mirko pays A only for the first ordered meal, while B prices apply for all other meals.
Mikro can't decide how many meals to order. In order to make his decision easier, he has asked you to compute, for each k between 1 i N (inclusive), the minimum total price for k ordered meals. Mirko doesn't care which particular meals he orders or in which order he orders them, however he won't order the same meal twice. Order, order, order.

The first line of input contains the positive integer N (2 ≤ N ≤ 500 000), the number of different meals offered by the restaurant.
Each of the following N lines contains two positive integers, Ai and Bi(1 ≤ Ai, Bi ≤ 1 000 000 000), the prices for meal i as described above.

Output must consist of N lines, where line k contains the minimum price for ordering exactly k different meals.

Clarification of the first example:
k = 1: Mirko pays A2 = 9 for the starting meal 2.
k = 2: Mirko pays A1 = 10 for the starting meal 1, then B2 = 3 for meal 2.
k = 3: Mirko pays A1 = 10 for the starting meal 1, then B2 = 3 for meal 2, and finally B3= 5 for meal 3.