3833. [雅礼集训 2017 Day5] 珠宝

【题目描述】

$Miranda$ 准备去市里最有名的珠宝展览会，展览会有可以购买珠宝，但可惜的是只能现金支付，$Miranda$ 十分纠结究竟要带多少的现金，假如现金带多了，就会比较危险，假如带少了，看到想买的右买不到。展览中总共有 $N$ 种珠宝，每种珠宝都只有一个，对于第 $i$ 种珠宝，它的售价为 $C_i$ 万元，对 $Miranda$ 的吸引力为 $V_i$ 。$Miranda$ 总共可以从银行中取出 $K$ 万元，现在她想知道，假如她最终带了 $i$ 万元去展览会，她能买到的珠宝对她的吸引力最大可以是多少？

【输入格式】

第一行两个整数 $N$ 、 $K$ 。

接下来 $N$ 行，每行两个整数 $C_i$ 、 $V_i$ 。

【输出格式】

输出一行 $K$ 个整数，对于第 $i$ 个数，表示假如 $Miranda$ 带了 $i$ 万元现金，她能买到的珠宝对她的吸引力最大可以是多少。

【样例1输入】

5 10
3 2
1 48
3 25
2 76
4 83

【样例1输出】

48 76 124 124 131 159 207 207 207 232

【样例2】

点击下载样例2

【数据规模与约定】

对于 $20\%$ 的数据， $N, K \leq 10000$ ；

对于另外 $20\%$ 的数据， $C_i = V_i$ ；

对于 $100\%$ 的数据， $1 \leq N \leq 1000000, 1 \leq K \leq 50000, 1 \leq C_i \leq 300, 0 \leq V_i \leq 10 ^ 9$ 。