01背包

题目描述

给定$n$个物品，如何得到背包容量分别为$1$,$2$,$\ldots$,$m$的最大价值（每一件物品只能取一次，不同的背包容量相互之间均为独立的问题）。

输入格式

第一行两个正整数$n$，$m$，代表物品数量和背包的最大容量；

接下来$n$行，每行两个整数$s$，$v$，分别代表每个物品的体积和价值。

输出格式

输出$m$个数，分别表示背包容量为$1$,$2$,$3$,$\ldots$,$m$时的最大价值。

数据范围与提示

• 对于$20\%$的数据，$n \times m < 100000$；
• 对于$100\%$的数据，$1 \leq n \leq 10^{6}$，$1 \leq m \leq 10^{5}$，$1 < s < 300$，$1 \leq v \leq 10^{9}$。

样例

4 9
2 8
1 1
3 4
5 100

1 8 9 9 100 101 108 109 109