题目描述

原题出处：「NAIPC2016」Jewel Thief

Miranda 准备去市里最有名的珠宝展览会。展览会可以购买珠宝，但只能现金支付。Miranda 在纠结要带多少现金：带多了会有危险，带少了又可能买不到心仪的珠宝。

展览中总共有 $N$ 种珠宝，每种珠宝只有一个。对于第 $i$ 种珠宝，它的售价为 $C_i$ 万元，对 Miranda 的吸引力为 $V_i$。

Miranda 最多可以从银行取出 $K$ 万元。现在她想知道，如果她最终带了 $i$ 万元去展览会（$1 \leq i \leq K$），她能买到的珠宝对她的最大吸引力是多少？

输入格式

第一行两个整数 $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 10^6$
  • $1 \leq K \leq 5 \times 10^4$
  • $1 \leq C_i \leq 300$
  • $0 \leq V_i \leq 10^9$