#6039. 「雅礼集训 2017 Day5」珠宝

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

题目描述

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

输入格式

第一行两个整数 N K
接下来 N 行,每行两个整数 C_i V_i

输出格式

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

样例

样例输入

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

样例输出

48 76 124 124 131 159 207 207 207 232

数据范围与提示

对于 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