该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem B. Backpack of Capoo

Input file:　standard input
Output file:　standard output
Time limit:　2 seconds
Memory limit:　1024 megabytes

Hey, there. 请确保你在尝试本题前，已经了解动态规划中 01背包 的相关内容。

如果你不了解 动态规划 或者 01背包 算法，不妨先去 $\mathtt{oiwiki}$ 进行学习了解后再尝试本题。

动态规划：https://oi-wiki.org//dp/

01背包：https://oi-wiki.org//dp/knapsack/#0-1-%E8%83%8C%E5%8C%85

11月5日，是 龟神 学会 01背包 的一周年纪念日，01背包 是 背包问题 中最简单的问题。

01背包 的约束条件是给定几种物品，每种物品有且只有一个，并且有 权值 和 体积 两个属性。在 01背包 问题中，因为每种物品只有一个，对于每个物品只需要考虑选与不选两种情况。

如果不选择将其放入背包中，则不需要处理。如果选择将其放入背包中，由于不清楚之前放入的物品占据了多大的空间，需要枚举将这个物品放入背包后可能占据背包空间的所有情况。

现在 龟神 有 $n$ 只 猫猫虫，第 $i$ 只 猫猫虫 的体积为 $w_i$​，好看程度为 $v_i$​，他准备了一个容量大小为 $m$ 的背包。他可以从这 $n$ 只 猫猫虫 中任选若干只放入背包，但是所选 猫猫虫 的体积总和不能大于背包的容量 $m$，龟神 想要让所选 猫猫虫 的好看程度总和最大化。

他运用自己一年前刚刚学会的 01背包 知识，快速算出了他能用他的背包装下 猫猫虫 好看程度总和的最大值。

现在 龟神 有了一个新的问题，我们定义原问题的答案，即所选 猫猫虫 好看程度总和的最大值为 $Val_{\max}$​。

定义从这 $n$ 只 猫猫虫 中去掉第 $i$ 只 猫猫虫 后，从剩余 $n - 1$ 只 猫猫虫 中任选若干个放入背包，所选 猫猫虫 好看程度总和的最大值为 $Val_i'$​。

若 $Val_i'​<Val_{\max}$​，则称第 $i$ 只 猫猫虫 为一只 "必选猫猫虫"。

龟神 现在获得了调整 猫猫虫 好看程度的机会，他想要知道，对于第 $i$ 只 猫猫虫，在它初始好看程度的基础上，再加上多少，该 猫猫虫 就能够成为一只 "必选猫猫虫"。

Input

第一行包含两个正整数 $n, m$ $(1 \leq n, m \leq 100)$。

接下来包含 $n$ 行，每行包含两个正整数 $w_i​$ $​(1 \leq w_i \leq m)$，$v_i$ $(1 \leq v_i​ \leq 10^9)$，表示每只猫猫虫的体积以及好看程度。

Output

输出 $n$ 行，每行一个整数，第 $i$ 行表示在它初始好看程度的基础上，再加上多少，该 猫猫虫 就能够成为一只 "必选猫猫虫"。

特别的，如果该 猫猫虫 已经是一个 "必选猫猫虫"，则输出 $0$。

Example

Hint

注意只有当 $Val_i' ​<Val_{\max}$ ​时，才称其为 "必选猫猫虫"，与原本的最大值完全相等时说明该 猫猫虫 的好看程度还需要再加上 $1$ 点。