Jewel Thief

A large museum opened an exhibit of jewelry gathered from around the world. Edward Terrenando, a thief, is planning the biggest theft of his career there.

Edward wants the total value of the stolen jewels to be as large as possible, so he has to choose carefully which jewels to take.

Edward owns one knapsack of each size $1, 2, 3, \dots, k$. A knapsack of size $s$ holds any set of jewels whose sizes sum to at most $s$. For every knapsack size, find the maximum total value of jewels it can hold.

The same jewel cannot go into one knapsack twice, and each knapsack is a separate problem.

The first line contains two integers $n$ and $k$ separated by a space ($1 \le n \le 1{,}000{,}000$, $1 \le k \le 100{,}000$), the number of jewels and the largest knapsack size.

Each of the next $n$ lines describes one jewel with two integers $s$ and $v$ separated by a space ($1 \le s \le 300$, $1 \le v \le 10^9$), the size and the value of that jewel.

Print $k$ integers on one line, separated by single spaces. The $i$-th integer is the maximum total value of jewels that fits in a knapsack of size $i$.