题目描述

小 Z 正在玩一款冒险游戏，角色的负重上限为 $W$。

地图上散落着 $n$ 种道具，每种道具最多拾取一个。第 $i$ 种道具重量为 $w_i$，拾取后可以增加 $v_i$ 战力值。游戏规则：拾取道具总重量不能超过负重上限，目标是让总战力值最大化。

当前可能有多种拾取组合，都能达到全场最高战力。游戏设计师需要调整道具属性：对于每一个道具，最少将它的战力值提升多少，才能让这个道具成为「必备道具」—— 只要玩家想拿到最高战力，就必须拾取它？（提升某件道具战力值时，其他道具都维持原样不变）

输入格式

第一行，$2$ 个正整数 $n, W$，表示道具的数量与小Z的负重上限

接下来 $n$ 行，每行两个数字 $w_i,v_i$，表示每件道具的重量与战力值

输出格式

$n$ 行整数，表示每件道具至少提高多少战力值，会成为必备道具

输入输出样例

3 5
3 3
2 1
2 1

0
0
1

样例 $\tt \#1$说明

最优方案下，最后能选择的方案有：第一件+第二件、第一件+第三件。所有第一件已经是必选的，不需额外增加战力值

第二物品，只需增加 $1$ 的战力值，就可以让自己成为必选；第三件物品同理。

5 9
2 10
4 10 
1 10
5 10
9 10

0
1
0
1
21

数据范围

所有数据保证: $w_i\le W$