Description

舒克和贝塔终于下定决心要去营救被关押在众猫聚居的 A 城中的大米同志。

A 城的构造是很奇怪的。 A 城中的所有 N 栋建筑沿着一条直线排列，而且没有两栋楼的高度是相同的。而大米同志就被关押在其中的某栋建筑中。每一栋建筑的顶上都是有一些猫们在看守的。如果按照从一端到另一端的顺序将所有的建筑编号为 1 到 N, 那么第 i 栋建筑的高度为 Hi，0顶上开始时的猫的数量为 Ci 。

每一只猫不但可以看守住其所在建筑的楼顶，还可以看守住一些比它所在建筑要低的楼的楼顶。前提是没有被其他楼所挡住。A 城中的建筑都是很高的，高到可以忽略它们之间的距离和它们的水平面面积。于是可以认为，楼 i 上的猫能看守楼 j 的楼顶，当且仅当楼 i 的高度不低于楼 j，且楼 i 到楼 j 之间的所有楼房的高度都低于楼 i 。 现在, 神勇的贝塔同学已经潜入了 A 城内部营救大米同志，而舒克则负责驾驶直升机提供空中支援。按照约定，贝克找到并救出大米后会爬上楼顶施放信号让舒克前来接应。

舒克的飞机上装备有 K 枚鱼肉炸弹。每一枚鱼肉炸弹都可以在被投放到某一座楼的楼顶一段时间之后使该楼所有猫丧失行动能力。由于舒克并不知道贝塔会登上哪座楼的楼顶， 所以现在他决定减少在最坏情况下与贝塔汇合时被发现的可能。具体来说，假设第 i 栋楼被 Si 只猫看守（注意 Si 只猫包括在该楼上的 Ci 只以及在其他楼上所有能看守该楼顶的猫），他希望便用这 K 枚炸弹使得 Si 中的最大值最小。聪明的舒克很快就通过正确地选择炸弹投放地点完成了这一目标。你能吗？

Input

第一行有两个整数N和K。 第二行至第N+1行每行有两个整数，依次为编号为1的楼到编号为N的楼的高度(Hi)和楼顶的猫数(Ci)。 数据规模: 1<=N<=100000 1<=K<=5 1<=Hi<=1000000000 0<=Ci<=1000000000

Output

在这个题目中，你只需输出一个整数，表示使用K枚炸弹所能达到的Si中的最大值最小能是多少。

Sample Input

样例1

3 2

1 2

3 1

2 2

样例2

3 1

1 2

3 1

2 2

样例3

5 1

1 4

5 1

3 4

4 2

2 5

Sample Output

样例1

1

(说明:可投放在第一座楼和第三座楼上)

样例2

2

(说明:可投放在第二座楼上)

样例3

6

(说明:可投放在第四座楼上)