Read problems statements in Mandarin Chinese and Russian as well.

Mike takes part in programming contests. His favourite topic is dynamic programming(DP). As he said, that he likes problems on DP, because "you spend a lot of time on thinking and a little time on coding".
In this problem you are to solve a version of the knapsack problem(link), one of the most famous examples of DP problem.
You are given N items, each has two parameters: a weight and a cost. Let's define M as the sum of the weights of all the items.
Your task is to determine the most expensive cost of a knapsack, which capacity equals to 1, 2, ..., M. A cost of a knapsack equals to the sum of the costs of all the elements of the knapsack. Also, when you have a knapsack with a capacity is equal to C, then you can fill it with items, whose sum of weights is not greater than C.

------ Input ------

The first line of the input contains one integer N, denoting the number of the items.
The next N lines contain two integers W and C each, denoting the weight and the cost of the corresponding item.

------ Output ------

For each capacity C (1 ≤ C ≤ M) of the knapsack, output a single integer - the most expensive cost for that capacity.

------ Constraints ------

3 ≤ N ≤ 100000;
1 ≤ W ≤ 2, for each item;
1 ≤ C ≤ 10^{9}, for each item.

------ Example ------

Input:
5
1 1
2 2
2 3
2 4
2 5

Output:
1 5 6 9 10 12 13 14 15

------ Explanations ------

In the test case, M equals to 9.

For C = 1, it's optimal to choose {1} items;

For C = 2, it's optimal to choose {5} items;

For C = 3, it's optimal to choose {1, 5} items;

For C = 4, it's optimal to choose {4, 5} items;

For C = 5, it's optimal to choose {1, 4, 5} items;

For C = 6, it's optimal to choose {3, 4, 5} items;

For C = 7, it's optimal to choose {1, 3, 4, 5} items;

For C = 8, it's optimal to choose {2, 3, 4, 5} items;

For C = 9, it's optimal to choose {1, 2, 3, 4, 5} items.

见题面

见题面