题目描述

请注意数据范围。

给定 $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$ 时的答案。

3 6
1 1
2 2
3 2

1
2
3
3
4
5

数据规模与约定

本题应用捆绑测试。

1. 对于 $1\%$ 的数据，为样例。
2. 对于另外 $9\%+19\%$ 的数据，$|\{w_i\}|\le10$，$w_i\ge10^4$。
3. 对于另外 $8\%+10\%$ 的数据，$w_i\ge10^4$。
4. 对于所有的数据，$1\le n,m,w_i\le 10^6$，$1\le v_i\le10^9$，$|\{w_i\}|\le100$。