Reed Dacht 是一位在家工作的自由职业图书编辑。各家出版社寄给他书稿，并附上希望收到编辑意见的截止日期。Reed 阅读非常严谨，从不同时阅读超过一本书，因此他只有在读完上一本书后才会开始阅读下一本。他愿意改变阅读速度（每天阅读的页数），但为了对每位客户公平，他坚持对所有书使用相同的阅读速度。

前几天，Reed 接到了大量的编辑请求，遇到了一些麻烦。他认为自己无法在规定的截止日期前读完所有的书。他可以将阅读速度设置得足够快以按时完成所有工作，但这可能会影响编辑的准确性（并严重损害他的视力）。为了避免这种情况，他可以选择较慢的阅读速度，但这样会有太多的编辑工作超过截止日期。他决定采取折中方案：他愿意让少数几本书超过截止日期（这样只会惹恼少数客户），并将阅读速度设置为每天阅读的最少页数，使得超过截止日期的书不超过 $m$ 本。那么这个阅读速度应该是多少呢？这就是你需要解决的问题。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$，其中 $n$ ($1 \le n \le 10^5$) 是需要编辑的书的数量，$m$ ($0 \le m < n$) 是 Reed 允许延期的编辑工作数量。接下来有 $n$ 行，每行描述一本书。每行包含两个整数 $l$ 和 $d$，其中 $l$ ($1 \le l \le 10^9$) 是书的长度（页数），$d$ ($1 \le d \le 10^4$) 是该书的截止日期（距离截止还有多少天）。

输出格式

输出允许不超过 $m$ 个编辑工作延期的最小整数阅读速度（页数/天）。

样例

样例输入 1

3 1
450 9
500 6
300 4

样例输出 1

84