g6-08126. 价值速查表 未做

快递站有 $n$ 种货物，第 $i$ 种货物每件重 $w_i$ 千克、运费补贴 $v_i$ 元，每种货物货源管够，想装几件就装几件。货车最大称重为 $W$ 千克。

站长想打印一张速查表贴在墙上：对每个整数承重 $v=0,1,2,\dots ,W$，标出承重不超过 $v$ 时能运走货物的最大总补贴。请你帮他生成这张表。

第一行两个整数 $n$、$W$。

接下来 $n$ 行，每行两个整数 $w_i$、$v_i$。

一行 $W+1$ 个整数，第 $v$ 个数（从 0 开始计数）表示承重不超过 $v$ 时的最大总补贴，用空格分隔。

输入 1

3 10
2 3
3 4
4 5

输出 1

0 0 3 4 6 7 9 10 12 13 15

$f(2)=3$（一件第一种）；$f(3)=4$（一件第二种，比两件第一种更优）；$f(5)=7$（$2+3$ 搭配）；……$f(10)=15$（五件第一种，重量恰好 $10$）。

$1\le n\le 600$，$1\le W\le 2\times 10^5$，$1\le w_i\le W$，$0\le v_i\le 10^9$。保证答案不超过 $10^{18}$。