#6081. ZQC 的女装

内存限制:256 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: yanQval

题目描述

题目来自: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