题目描述

夏季促销开始了！

佩奇计划购买一些学习软件，她共有x元的预算，该平台上所有的n个学习软件均有折扣，标号为i的游戏的原价ai元，现价只要bi元（也就是说该游戏可以优惠ai-bi元, 每款游戏最多只能购买一次），并且佩奇购买该学习软件能获得快乐值为wi。

由于优惠的存在，佩奇可能做出某些冲动消费，这样可能导致最终买软件的总费用超过出预算，但只要满足"获得的总优惠金额不低于超过预算的总金额"，那在佩奇心理上就不会觉得吃亏 (买到就是赚到!!)。

现在佩奇希望在心理上不觉得吃亏的前提下，获得尽可能多的快乐值。

输入格式

第一行包含两个数n和x。接下来n行包含每个软件的信息，原价ai，现价bi，能获得的快乐值为wi。

输出格式

输出一个数字，表示佩奇能获得的最大快乐值。

输入输出样例

样例输入1

4 100 

100 73 60 

100 89 35 

30 21 30 

10 8 10

样例输出1

100

样例输入2

2 100 

100 30 35 

140 140 100

样例输出2

135

说明

【样例3分析】买1，3，4三款软件，获得总优惠38元，总金额102元超预算2元，满足条件，获得100快乐值。

数据规模

对于30%的数据， n<=15;

对于60%的数据， n<=100;

对于100%的数据， 1<=n<=5000; 0<=x<=10^4; 0<=bi<=ai<=500; 1<=wi<=10^9