F. Knapsack One Million
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

The Orlando City Plaza Casino has released a new game for their patrons to enjoy: Knapsack One Million! In this game, a million types of random chips will be dispensed. Each type of chip will have a random size and a random value, and a million of each type of chip will be dispensed. You are then given a Knapsack One Million, which is a bag that can hold a set of chips whose sum of sizes is at most one million; that is, the capacity of the knapsack is one million.

Before testing your luck in this game, you want to analyze the best-case performance you could have in a game; however, you worry the casino might attempt to cheat by giving you a bag with a more limited capacity than advertised. Thus, for a given set of chips, you want to compute the maximum value you can achieve for all knapsack capacities between $$$1$$$ and $$$10^6$$$, inclusive.

Input

The first line of input will consist of a single integer $$$n$$$ ($$$n = 10$$$ or $$$n = 10^6$$$) — the number of chips. In all cases other than the sample, $$$n$$$ will equal $$$10^6$$$.

The following $$$n$$$ lines will consist of two integers $$$s_i$$$ and $$$v_i$$$ — the size and value of the $$$i$$$th type of chip.

Each case (except for the sample) will be selected from a set of $$$10^6$$$ generated cases. Each case was generated such that $$$s_i$$$ and $$$v_i$$$ are uniformly randomly generated from the range $$$1$$$ to $$$n$$$, inclusive. It is guaranteed that each value is generated independently. Please read the note for more details.

Output

Output a single line consisting of $$$n$$$ integers where for each $$$i$$$ from $$$1$$$ to $$$n$$$, inclusive, the $$$i$$$th integer corresponds to the maximum value of chips you can choose such that the sum of weights of the chips is at most $$$i$$$.

Example
Input
10
7 2
1 3
8 5
4 6
9 10
5 4
7 9
6 1
2 10
8 3
Output
3 10 13 20 23 30 33 40 43 50
Note

Each testcase, except for the sample, was generated using C++'s built-in "std::mt19937" (Mersenne Twister) in combination with "std::uniform_int_distribution". The random number generator was seeded with an integer between $$$1$$$ and $$$10^6$$$ (inclusive), though the seed was not necessarily chosen at random. Items were generated independently at random: the first $$$2 \cdot 10^6$$$ values produced were used as the sizes and values of each chip type. Specifically, for the $$$i$$$-th chip, the size is the $$$(2i - 1)$$$-th value and the value is the $$$(2i)$$$-th value generated.