g6-08091. 预算价目表 未做

奶茶店要出一张加料价目表：店里有 $n$ 种小料，第 $i$ 种每份重 $w_i$ 克、值 $v_i$ 分，每种小料都管够，一杯里想加几份就加几份。杯子的容量可能是 $0,1,\dots ,V$ 克中的任意一种，店长想对每种容量都提前算好：这一杯最多能值多少分？请按容量从小到大的顺序依次输出。

第一行两个整数 $n,V$。接下来 $n$ 行，每行两个整数 $w_i,v_i$。

一行 $V+1$ 个整数，用空格分隔。

输入 1

2 6
2 3
3 4

输出 1

0 0 3 4 6 7 9

容量 2 克时加一份重 2 的小料值 3 分；容量 4 克加两份值 6 分；容量 6 克加三份值 9 分；容量 3、5 克时再补一份重 3 的小料，分别得 4 分和 7 分，所以答案是 $0,0,3,4,6,7,9$。

$1\le n\le 100$，$0\le V\le 2000$，$1\le w_i\le 10^9$，$0\le v_i\le 10^9$。