A6678. 「雅礼集训 2017 Day5」珠宝 /「NAIPC2016」Jewel Thief
编程题
提高+/省选-
知识点
题目描述
**原题出处：「NAIPC2016」Jewel Thief**
Miranda 准备去市里最有名的珠宝展览会，展览会有可以购买珠宝，但可惜的是只能现金支付，Miranda 十分纠结究竟要带多少的现金，假如现金带多了，就会比较危险，假如带少了，看到想买的又买不到。展览中总共有 $ N $ 种珠宝，每种珠宝都只有一个，对于第 $ i $ 种珠宝，它的售价为 $ C_i $ 万元，对 Miranda 的吸引力为 $ V_i $。Miranda 总共可以从银行中取出 $ K $ 万元，现在她想知道，假如她最终带了 $ i $ 万元去展览会，她能买到的珠宝对她的吸引力最大可以是多少？
Miranda 准备去市里最有名的珠宝展览会，展览会有可以购买珠宝，但可惜的是只能现金支付，Miranda 十分纠结究竟要带多少的现金，假如现金带多了，就会比较危险，假如带少了，看到想买的又买不到。展览中总共有 $ N $ 种珠宝，每种珠宝都只有一个，对于第 $ i $ 种珠宝，它的售价为 $ C_i $ 万元，对 Miranda 的吸引力为 $ V_i $。Miranda 总共可以从银行中取出 $ K $ 万元，现在她想知道，假如她最终带了 $ i $ 万元去展览会，她能买到的珠宝对她的吸引力最大可以是多少？
输入格式
第一行两个整数 $ N $、$ K $。
接下来 $ N $ 行，每行两个整数 $ C_i $、$ V_i $。
接下来 $ 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
说明/提示
对于 $ 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 $。
对于另外 $ 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 $。