自助者天助

【题目背景】

蜀魏两军经过数日的鏖战，沙场死伤遍野，惨不忍睹，均退回营寨修养，以备再战。一日，军师孔明，夜观天象，预测隔日将有西北风大作，遂决定派出一支神兵，驾驶刚刚研发的翼装，趁夜色，奇袭敌营。 魏军获悉将被偷袭，遂加强了防御，急煞汉军师。

【题目描述】

魏军防守严密，军师怎敢懈怠，每日苦练破敌算法，无时不忘优化代码。

几日下来，军师胸有成竹，闲暇之余，行至山中游玩，不时有阵阵果香扑鼻，甚是喜人，闻香而去，一万亩野生幸运果园映入眼帘，此果，气香味美，强身提神，军师感叹，实乃天助我汉军也。

军师速令军士准备马车，采摘幸运果，犒劳三军。为方便军士们采摘到最佳果子，军师给大家教授了轻松预估每个果子重量和美味度的方法，军士们迅速掌握，开工！

请你帮助军士们如何在保证果子总重量不超过所有马车总载重量的前提下，使所有采摘到的果子的美味度之和最大。

【输入格式】

第一行，两个正整数$n$和$m$，分别表示幸运果总个数和马车总载重量；

接下来$n$行，第$i+1$行包含两个正整数$w$和$v$，分别表示第$i$个幸运果的重量和美味度；

【输出格式】

一个正整数，表示符合题意的幸运果美味度最大和。

【样例输入】

3 3
1 2
2 3
3 6

【样例输出】

6

【样例说明】

（$1$）只摘第$1$个，总美味度$2$；（$2$）只摘第$2$个，总美味度$3$；

（$3$）摘第$1$，$2$个，总美味度$5$；（$4$）摘第$3$个，总美味度$6$；

故输出$6$。

【数据规模与约定】

$30$%的数据，$1<=n<=16，1<=m<=3000$；

$60$%的数据，$1<=n<=1000，1<=m<=10000$；

$100$%的数据，$1<=n<=30000，1<=m<=30000，1<=w,v<=1000$；

$100$%的数据，幸运果不超过$100$种，重量和美味度均相同的两个果子视为同一种，除此之外视为不同种。

【来源】

$Mr$ $Chengyy$