说明

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

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

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

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

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

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

输入格式

输入第一行包含两个整数 $n,m$，分别表示老师和同学的人数

接下来 $n$ 行每行包含两个整数 $a_i,b_i$，含义如题

测试点编号	$n \leq$	$m \leq$	$a_i, b_i \leq$	特殊性质
$1$	$10$	$10$	$1000$
$2$	$1000$	$1000$	$1000$	$a_i$ 之和大于 $m$
$3 \sim 4$	$10^5$	$10^{10}$	$100000$	所有 $b_i$ 均相等
$5 \sim 6$	$1000$	$1000$	$1000$
$7 \sim 8$	$10^5$	$10^5$	$1000$
$9 \sim 10$	$10^5$	$10^{10}$	$10^9$

</span>

输出格式

输出 $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]$

来源

CSP模拟赛