01背包

【题目描述】

OIP马上就要到了，爱思考的kcz在复习$01$背包时想到了这样一个问题，给定$n$个物品，如何在最短的时间内得到背包容量分别为$1，2，...，m$的最大价值（每一件物品只能取一次，不同的背包容量相互之间均为独立的问题）。 聪明的kcz马上就想到了一个绝妙的方法，但是他觉得你不够机智，所以他把物品的体积都缩小了来考考你。

【输入】

第一行两个正整数$n，m$，表示物品数量和背包的最大容量。 接下来$n$行，每行两个整数$s，v$，分别表示每个物品的体积和价值。

【输出】

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

【输入样例】

4 9
2 8
1 1
3 4
5 100

【输出样例】

1 8 9 9 100 101 108 109 109

【提示】

【数据规模】 20%的数据：$n×m≤100000$。 100%的数据：$1≤n≤10^6;1≤m≤10^5;1≤s≤300;1≤v≤10^9$。