大样例下载

题目描述

有 $N$ 种物品，每种物品有无数件，其中第 $i$ 种物品的单件重量为 $W_i$, 单件价值为 $V_i$。

有 $M$ 个背包，第 $j$ 个背包的载重量恰好为 $j$$（1 ≤ j ≤ M）$。

对于每一个背包，你可以选择若干种物品装入背包。同一个背包中，同一种物品最多装一件，且装入背包的物品的总重量不能超过背包的载重量。

问：对于第 $x$ 个背包，你可以装入其中的物品的总价值最大是多少？

输入格式

第一行：包含两个整数 $N, M$;

接下来 $N$ 行：每行包含两个整数 $W_i, V_i$。

输出格式

一行，共 $M$ 个整数，依次表示 $x = 1, 2, ……, M$ 时的答案。

样例输入

5 5
1 1
1 2
2 1
5 2
3 6

样例输出

2 3 6 8 9

数据范围

100% 的数据：$1 ≤ N ≤ 10^6, 1 ≤ M ≤ 5×10^4, 1 ≤ W_i ≤ 300, 0 ≤ V_i ≤ 10^9$。其中：

有 20% 的数据，$N, M ≤ 10^4$；

另有 20% 的数据：$W_i = V_i$；