题目描述

你们班的同学对于报名参赛并不是非常感冒，班主任似乎看穿了大家的心思，于是决定给每个项目设置参赛积分，积分可以兑换奖品。

你非常心动，想看看报名哪些项目可以获取最多的积分，但你的体力值让你的选择变的有限。

输入格式

第一行包含两个整 $N$ 和 $T(1≤ N ≤20，1≤T≤100000)$ 分别表示体育节的项目数和你的最大体力值。

接下来 $N$ 行，每行两个整数 $a_i$ ，$w_i$表示该项目需要消耗的体力和可以获得的积分

输出格式

一个整数，表示你在有限的体力值下可以获得的最大积分

样例 #1

样例输入 #1

3 10
3 5
7 15
5 12

样例输出 #1

20