Knapsack Problem

All submissions for this problem are available.
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.
Author:  kostya_by 
Tester:  rustinpiece 
Editorial  http://discuss.codechef.com/problems/KNPSK 
Tags  cook47, easymedium, greedy, kostya_by, sorting 
Date Added:  31052014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 