sad

Time Limit: 8000MS

Memory Limit: 65536KB

Description

金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算”。今天一早金明就开始做准备,但是他想买的东西太多了,共N件。于是,他决定分组买这些东西。他把每件物品规定了一个重要度C,此外他还从因特网上查到了每件物品的价格(都是整数元)F,并且给每件物品都编了号,为1到N。金明的分组规则如下: 1、每一组中的物品编号必须连续,即要类似这样分:(1,2,....i),(i+1,i+1,...j)....(k,k+1...n) 2、对于任意一对编号(i,j i<j且1<=i,j<=n),如果物品i被分在p组,j被分在在q组中,且(p<q),那么必须要有Fi>Cj。 3、对于每一组K,金明定义这一组中物品的重要度的最大值为这一组的重要度Mi,这一组中物品所有物品价格之和为这一组的价格Si。在妈妈的限制下,所有的组的Mi之和不能超过一个上限limit。 而金明在分组的过程中则希望所有的Si中的最大值又要尽量小,这样妈妈就不会太在意钞票这个问题了,哈哈哈哈,现在的问题是 请你帮助金明设计一个满足要求的分组单。

Input

多组测试数据。 对于每一组测试数据: 第一行包括两个正整数N,limit(0<=N<=10^5,limit<=2^31-1) 接下来的N行每行包括两个正整数Ci,Fi分别表示第i件物品的价格和重要度 (0<=Ci,Fi<=10000)

Output

为了简单起见,金明不需要你输出整个分组单啦,输出你的分组中最大的S就行了。 如果没有合适的方案请输出 -1 每个Case占一行

Sample Input

4 6
4 3
3 5
2 5
2 4

Sample Output

9

Hint

n=0输出0

Source

None

提交代码