[문제 요약] 모든 음식들에는 두 가지 가격표가 있습니다.

가격표A는 가장 처음 주문하는 음식에 적용되고 가격표B는 다른 음식들에게 적용됩니다. 1개, 2개, 3개 ... N개의 음식을 주문하는 모든 경우에 대해 지불해야하는 돈을 최소화해 출력하세요

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.

출력

입출력 예

input

3 
10 5 
9 3 
10 5

output

9 
13 
18

input

2 
100 1 
1 100

output

1 
2

input

5 
1000000000 1000000000 
1000000000 1000000000 
1000000000 1000000000 
1000000000 1000000000 
1000000000 1000000000

output

1000000000 
2000000000 
3000000000 
4000000000 
5000000000

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.

출처:coci/2012-2013/contest2 4/6
요약:ladown21