Problem Description: 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 (15 CSM) of the knapsack, output a single integer - the most expensive cost for that capacity. Example: Input: 5 11 22 23 24 25 Explanation: 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 Output 1: 1 5 6 9 10 12 13 14 15 Hint: you may print the last row from the table. Problem Description: 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 (15 CSM) of the knapsack, output a single integer - the most expensive cost for that capacity. Example: Input: 5 11 22 23 24 25 Explanation: 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 Output 1: 1 5 6 9 10 12 13 14 15 Hint: you may print the last row from the table
