U138769 [W1] 控

**请注意数据范围。** 给定 $N$ 和 $M$ 以及 $N$ 个物品。每一个物品 $1\le i\le N$ 有一个重量 $w_i$ 和一个价值 $v_i$。对每一个 $1\le C\le M$，请选一个物品的子集，使得选取的 $w_i$ 之和不大于 $C$ 并且选取的 $v_i$ 之和最大。

第一行两个正整数，分别表示 $N$ 和 $M$。 接下来 $N$ 行，每行两个正整数，分别表示 $w_i$ 和 $v_i$。

输出 $M$ 行，第 $i$ 行输出 $C=i$ 时的答案。

**本题应用捆绑测试。** 1. 对于 $1\%$ 的数据，为样例。 2. 对于另外 $9\%+19\%$ 的数据，$|\{w_i\}|\le10,w_i\ge10^4$。 5. 对于另外 $8\%+10\%$ 的数据，$w_i\ge10^4$。 7. 对于所有的数据，$1\le N,M,w_i\le 10^6,1\le v_i\le10^9,|\{w_i\}|\le100$。