The grand museum has just announced a large exhibit on
jewelry from around the world. In the hopes of his potential
future prosperity, the worldrenowned thief and master criminal
Edward Terrenando has decided to attempt the magnum opus of his
career in thievery.
Edward is hoping to purloin a large number of jewels from
the exhibit at the grand museum. But alas! He must be careful
with which jewels to appropriate in order to maximize the total
value of jewels stolen.
Edward has $k$
knapsacks of size $1$,
$2$, $3$, up to $k$, and would like to know for each
the maximum sum of values of jewels that can be stolen. This
way he can properly weigh risk vs. reward when choosing
how many jewels to steal. A knapsack of size $s$ can hold items if the sum of sizes
of those items is less than or equal to $s$. If you can figure out the best
total value of jewels for each size of knapsack, you can help
Edward pull off the heist of the century!
Input
Each input will consist of a single test case. Note that
your program may be run multiple times on different inputs. The
first line of input will consist of two spaceseparated
integers $n$ and
$k$, where $n$ ($1
\le n \le 1\, 000\, 000$) is the number of jewels in the
exhibit, and $k$
($1 \le k \le 100\, 000$)
is the maximum size of knapsack available to Edward. The next
$n$ lines each will
describe a jewel. Each line will consist of two spaceseparated
integers $s$ and
$v$, where $s$ ($1
\le s \le 300$) is the size of the jewel, and
$v$ ($1 \le v \le 10^9$) is its value. Each
jewel can only be taken once per knapsack, but each knapsack is
an independent problem.
Output
Output $k$ integers
separated by whitespace. The first integer should be the
maximum value of jewels that will fit in a knapsack of size
$1$. The second should be
the maximum value of jewels in a knapsack of size $2$, and so on.
Sample Input 1 
Sample Output 1 
4 9
2 8
1 1
3 4
5 100

1 8 9 9 100 101 108 109 109

Sample Input 2 
Sample Output 2 
5 7
2 2
3 8
2 7
2 4
3 8

0 7 8 11 15 16 19

Sample Input 3 
Sample Output 3 
2 6
300 1
300 2

0 0 0 0 0 0
