Background

Special for beginners, ^_^

Description

寒假快结束乐，有些oier沉溺于打睿爸信奥的比赛，参加睿爸信奥的培训班，然后作业没怎么写，眼看假期余额不足，不抓紧赶出来，无法向老师交差。好在有钱能使鬼推磨，只要舍得出点压岁钱，小明同学愿意帮助代抄作业，勤工俭学，挣点零花钱，弥补全部上交的压岁钱的不足。当然，代抄作业是按页收费的，而且没有按期抄完的作业是不能收费的。小明把代抄作业的消息，通过微信发给了他的几个狐朋狗友，很快，大量业（财）务（源）滚滚而来。然后小明数了一下，发现他接的活太多了，根本抄不完。他决定两手抓，一是把原来的985工作制改为997工作制。此外，每违约一单，就会被同学毒打一顿，因为该同学没完成作业，老师会告诉家长，所以会被家长暴打一顿，然后该同学就拿小明出气。假设小明最多可以承受m顿毒打，问他每天至少要完成多少页。

Format

Input

第一行两个整数n（不超过1e5）和m，分别表示小明接到的业务数量和可以承受的毒打数量，接下来n行，每行两个整数l（不超过1e9）和d（不超过1e4），分别表示每笔业务有多少页和截止日期。

Output

输出最小的整数x，每天抄x页可以保证小明挨打不超过m顿。

Samples

3 1
450 9
500 6
300 4

84

Limitation

1s, 1024KiB for each test case.