背景

深秋的午后，阳光斜斜地淌进窗棂，落在你刚泡好的红茶杯里，漾开一圈琥珀色的光晕。我翻着旧相册，指尖停在那张褪色的合影——那年冬夜，你裹着我的围巾，哈着白气帮我捡散落在雪地里的书本，睫毛上的雪粒像碎钻。原来有些瞬间，早已在时光里镀上了暖色调。

我总爱抱怨你记性差，却忘了你记得我不吃香菜，记得我来例假要喝红糖姜茶，记得我提过一次的小众乐队，会悄悄买好演唱会门票。上次我加班到深夜，推开门就撞进满室饭香，你举着刚炒好的青菜，围裙上还沾着面粉：“怕你饿，熬了杂粮粥。”灯光下你眼角的细纹，比任何情话都动人。

我们很少说“我爱你”，却把深情藏在柴米油盐里。是清晨并肩走在菜市场，你会自然地接过我手里的菜篮；是雨天共撑一把伞，你的肩膀永远湿着半边；是我熬夜写稿时，桌角不断续杯的温水。这些细碎的温柔，像涓涓细流，汇聚成我们的人间烟火。

翻到相册最后一页，是昨天拍的照片：你在浇花，我举着手机偷拍，阳光落在你发梢，连灰尘都在发光。我抬头看你，你刚好回头，笑意漫过眼底。原来深情从不是轰轰烈烈的誓言，而是把“我们”藏在每一个寻常日子里，让岁月都带着甜。

描述

ACM招新赛使用 RG 监考系统，需要将参赛队员安排到系统中的虚拟赛场里，并为每个赛场分配一位监考老师。每位监考老师需要联系自己赛场内队员对应的教练们，以便发放比赛账号。为了尽可能减少教练和监考的沟通负担，我们要求赛场的安排满足以下条件：

• 每位监考老师负责的赛场里，队员人数不得超过赛场规定容量 C；
• 每位教练需要联系的监考人数尽可能少 —— 这里假设每所参赛学校只有一位负责联系的教练，且每个赛场的监考老师都不相同。
• 为此我们设计了多轮次排座算法，按照尚未安排赛场的队员人数从大到小的顺序，每一轮对当前未安排的人数最多的学校进行处理。记当前待处理的学校未安排人数为 n：
• • 如果 n≥C，则新开一个赛场，将 C 位队员安排进去。剩下的人继续按人数规模排队，等待下一轮处理；
• 如果 n<C，则寻找剩余空位数大于等于 n 的最小的赛场，将队员安排进去；
• 如果 n<C，且找不到任何非空的、剩余空位数大于等于 n 的赛场了，则新开一个赛场，将队员安排进去。 因为不因为什么所以我们必须写个程序来处理赛场安排问题。

格式

输入

输入第一行给出两个正整数 N 和 C，分别为参赛学校数量和每个赛场的规定容量，其中 0<N≤5000，10≤C≤50。随后 N 行，每行给出一个学校的缩写（为长度不超过 6 的非空小写英文字母串）和该校参赛人数（不超过 500 的正整数），其间以空格分隔。题目保证每所学校只有一条记录。

输出

按照输入的顺序，对每一所参赛高校，在一行中输出学校缩写和该校需要联系的监考人数，其间以 1 空格分隔。 最后在一行中输出系统中应该开设多少个赛场。

样例

10 30
zju 30
hdu 93
pku 39
hbu 42
sjtu 21
abdu 10
xjtu 36
nnu 15
hnu 168
hsnu 20

zju 1
hdu 4
pku 2
hbu 2
sjtu 1
abdu 1
xjtu 2
nnu 1
hnu 6
hsnu 1
16

提示

这一题可能需要用到 priority_queue，和queue一样都属于队列，但priority_queue为优先队列，(头文件和queue的相同)。

下面给出二者的一些不同点：

操作1：pop()

queue: 弹出队首元素

priority_queue: 弹出队列里值最大的元素

操作2：push()

queue: 将元素压进队列

priority_queue: 将元素压进队列里面，并自动排序(队首元素最大，队尾元素最小)。

操作3：front() / top()

queue: front() 获取队首元素

priority_queue: top() 获取队首元素(即值最大的元素)

用法：

1.定义优先队列

priority_queue<int>q;

2.将元素x压进优先队列

q.push(x);

3.弹出队首元素

q.pop();

4.获取队首元素

q.top();

（即：优先队列里面的元素是有序的，队首元素最大，队尾元素最小）

限制

1s, 1024KiB for each test case.