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

说明

徐老师的学校要进行体测了，现在学校安排了 $n$ 位老师来给同学们体测，由于学校人手不够，派出的老师有的是体育老师，有的是数学老师，每个人的专业能力不同

比如体育老师可以同时给十几个人同时测试，而数学老师可能同时只能关注两三个同学同时测试，毕竟专业不同嘛！

现在徐老师已经统计好了，每位老师的测试能力，第 $i$ 位老师可以同时给 $a_i$ 位同学进行测试，并且每位同学的测试需要花费 $b_i$ 分钟

现在有 $m$ 位同学需要测试，徐老师需要给他们安排队伍，徐老师安排的思路非常简单：每位同学依次安排到现在排队等待时间最短的老师处排队，如果有两位老师处的等待时间一样，则选择编号小的老师

现在徐老师想知道，分配完所有同学以后，每位老师处的排队人数分别是多少？

这里我们认为 $m$ 位同学全部都是同时到达的，分配完队伍后才会统一开始体测

输入格式

输入第一行包含两个整数 $n,m$，分别表示老师和同学的人数
接下来 $n$ 行每行包含两个整数 $a_i,b_i$，含义如题

输出格式

输出 $n$ 个整数，分别表示每个老师处的排队人数

样例

3 18
1 3
2 5
10 20

4 4 10

提示

首先一开始直接分配 $1$ 个人到 $1$ 号老师，$2$ 个人到 $2$ 号老师，$10$ 个人到 $3$ 号老师处
此时三个老师处的排队时间为 $[3,5,20]$
分配思路如下：
1. 分配 $1$ 个人到 $1$ 号老师处，三个老师处的排队时间为 $[6,5,20]$ 
2. 分配 $2$ 个人到 $2$ 号老师处，三个老师处的排队时间为 $[6,10,20]$
3. 分配 $1$ 个人到 $1$ 号老师处，三个老师处的排队时间为 $[9,10,20]$ 
4. 分配 $1$ 个人到 $1$ 号老师处，三个老师处的排队时间为 $[12,10,20]$ 
此时所有人都分配完成
最后所有队伍的人数为 $[4,4,10]$