题目描述

作为被召唤到异世界的勇者，你这一次的任务便是带领一支冒险者小队去挑战一座凭空出现的地下城，并击败其中的所有 BOSS。

地下城共有 n 层，每层都有一只 BOSS，第 i 层的 BOSS 的武力值为 a[i]，经验值为 b[i]。作为冒险者小队的队长，每次都是你先出手与 BOSS 交战。只要你的武力值不小于 BOSS 的武力值，你便可以直接击败它而不需要其他人出手，并且能够吸收这只 BOSS 的所有经验值转为自己的武力值（即你的武力值将会加上这只怪物的经验值）。而如果你无法直接击败它，才会让冒险者小队的其他成员一起参战。全员参战一定能够击败 BOSS，但同时你也将无法吸收这只 BOSS 的经验值。

你们会按顺序从第 1 层开始一层一层向下挑战，并且只有在击败当前这一层的 BOSS 之后才可以前往下一层继续挑战。

尽管冒险者小队的成员们都非常可靠，但终究比不上身为勇者的你，如果大家长时间参战的话很容易会出现体力不支的情况，所以你最多只能让全员参战 m 次。

请问在开始挑战地下城之前，你的武力值应当至少为多少，才能够在保证全员参战最多 m 次的前提下击败所有 BOSS？

输入格式

第一行包含两个正整数 n, m，表示地下城的层数以及全员参战的最多次数。

接下来 n 行，第 i 行包含两个正整数 a[i], b[i]，分别表示第 i 层 BOSS 的武力值以及经验值。

输出格式

一个整数，表示在开始挑战地下城之前你的武力值所需要的最小值。

测试样例

输入样例：

3 1
2 3
7 7
6 1

输出样例：

3

样例提示

当你的初始武力值为 3 时：

对于第一只 BOSS，由于 3 ≥ a[1] = 2，你可以直接击败它，并且武力值变为 3 + b[1] = 3 + 3 = 6。 对于第二只 BOSS，由于 6 ＜ a[2] = 7，你无法直接击败它，于是让全员参战击败这只 BOSS，武力值不变。 对于第三只 BOSS，由于 6 ≥ a[3] = 6，你可以直接击败它。

说明

1 ≤ a[i], b[i] ≤ 1000000000

对于20%的数据 1 ≤ m ＜ n ≤ 2000

对于100%的数据 1 ≤ m ＜ n ≤ 200000

限制

时间限制：500 ms

内存限制：65536 KB