题目描述

题目来自：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$ 元时的答案。

样例

input

4 9
2 8
1 1
3 4
5 100

output

1 8 9 9 100 101 108 109 109