题目描述

题目来自：NAIPC 2016 Problem H. Jewel Thief

ZQC 来到商店给买女装，商店里有 $n \ (1 \leq n \leq 10 ^ 6)$ 件女装，第 $i$ 件女装的价格为 $w_i \ (1 \leq w_i \leq 300)$，萌值为 $v_i \ (1 \leq v_i \leq 10 ^ 9)$，由于 ZQC 是个非常精打细算的人，给定他的总预算 $k \ (1 \leq k \leq 100000)$，他希望知道对于每个 $[1,k]$ 中的整数 $i$，如果他带了 $i$ 元，他能买到的女装萌值之和最大是多少（钱可以不花完）。由于 ZQC 急着去 AK UOI，这个问题就交给你了。

输入格式

第一行 $n$ 和 $k$。
接下来 $n$ 行，每行 $w_i$ 和 $v_i$。

输出格式

一行 $k$ 个数，第 $i$ 个数表示带了 $i$ 元时的答案。

样例

4 9
2 8
1 1
3 4
5 100

1 8 9 9 100 101 108 109 109