U492147 【不是模板】01背包

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

~~就是普通的01背包问题~~ 给出 $n$ 个物品 , 每个物品有体积 $s_i$ 价值 $v_i$ , 对于 $i=1\cdots m$ 求容量为 $i$ 的背包最多能放多少价值 . 提示：注意数据范围 .

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

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

20%的数据：$n\times m \le 100000$ 100%的数据：$1\le n \le 10^6;1≤m≤10^5;1≤s≤300;1≤v≤10^9$ 如果需要题解，可以看[题解](https://www.cnblogs.com/youlv/p/18438068) 题目来自一本通高手训练，数据为自造