限时任务(Timed Tasks)

题目描述

在全新的YACS学习平台上，学生可以通过做题积攒经验值，更高的经验值可以获得全站更高的排名。

每月一次的限时双倍经验活动就要到了，在限时活动规定的时间段内完成的题目，均可获得双倍标准经验值的奖励，不过学生必须在完成一道题后才可以开始下一道题的挑战。如果开启一道题目的挑战时在规定活动时间段内，即使完成这道题时已经超过规定时间，则仍可获得双倍经验。每一题只有第一次完成时计算经验值，重复完成无效。

小爱参加了这个月的限时活动，该月限时活动时间段共 T 分钟，小爱可以挑战的题目共 n 题，其中第 i 题所需时间为 tᵢ，标准经验值为 eᵢ。请你帮助小爱计算一下，如何安排做题，才能使在活动时间内，获得的经验值尽可能的多，最多可以获得多少经验值？

输入格式

第一行：两个正整数 n 与 T； 第二行到第 n+1 行：每行两个正整数 tᵢ 与 eᵢ。

输出格式

输出能获得的最多经验值

数据范围

• 对于 30% 的数据，1 ≤ n ≤ 20
• 对于 60% 的数据，1 ≤ n ≤ 100
• 对于 100% 的数据，1 ≤ n ≤ 5000，1 ≤ T ≤ 10⁴，1 ≤ tᵢ ≤ 10³，1 ≤ eᵢ ≤ 10⁴

样例输入 #1

3 7
2 3
4 5
3 5

样例输出 #1

26

说明: 先做第1，第2题，完成第2题时正好是6分钟，此时开始做第3题，仍算入双倍经验。所以三道题都可以在活动时间内完成，获得经验为(3+5+5)×2=26

样例输入 #2

3 7
4 3
4 5
4 5

样例输出 #2

20

说明: 选择完成第2，第3题，共获得经验值(5+5)×2=20

知识点与难度

本题涉及的知识点从属于 GESP 6级，难度等级：⭐⭐⭐。

测试点分布