该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

T4. 竞赛得分 (contest)

题目描述

小蓝正在参加一场编程竞赛。竞赛共有 $N$ 道题，比赛总时间为 $T$ 分钟。第 $i$ 道题需要花费 $t_i$ 分钟来完成，完成后可以获得 $s_i$ 分。

每道题只能做一次，且一旦开始做一道题就必须连续做完，不能中途暂停换题。小蓝可以自由选择题目的顺序。

请你帮小蓝计算：在总时间不超过 $T$ 分钟的条件下，最多能获得多少分。

输入格式

第一行两个整数 $N, T$。

接下来 $N$ 行，每行两个整数 $t_i, s_i$。

输出格式

一行一个整数，表示最大得分。

样例

样例 #1

3 120
30 50
60 100
50 80

180

解释：选第1(30,50)和第2(60,100)总时间90得分150；选第1和第3总时间80得分130；选第2和第3总时间110得分180；全选140>120不行。最大180。

数据范围

对于全部数据，$1\le N\le 1000$，$1\le T\le 50000$，$1\le t_i\le T$，$1\le s_i\le 1000$。