CF542F.Quest

Polycarp is making a quest for his friends. He has already made n tasks, for each task the boy evaluated how interesting it is as an integer q__i, and the time t__i in minutes needed to complete the task.

An interesting feature of his quest is: each participant should get the task that is best suited for him, depending on his preferences. The task is chosen based on an interactive quiz that consists of some questions. The player should answer these questions with "yes" or "no". Depending on the answer to the question, the participant either moves to another question or goes to one of the tasks that are in the quest. In other words, the quest is a binary tree, its nodes contain questions and its leaves contain tasks.

We know that answering any of the questions that are asked before getting a task takes exactly one minute from the quest player. Polycarp knows that his friends are busy people and they can't participate in the quest for more than T minutes. Polycarp wants to choose some of the n tasks he made, invent the corresponding set of questions for them and use them to form an interactive quiz as a binary tree so that no matter how the player answers quiz questions, he spends at most T minutes on completing the whole quest (that is, answering all the questions and completing the task). Specifically, the quest can contain zero questions and go straight to the task. Each task can only be used once (i.e., the people who give different answers to questions should get different tasks).

Polycarp wants the total "interest" value of the tasks involved in the quest to be as large as possible. Help him determine the maximum possible total interest value of the task considering that the quest should be completed in T minutes at any variant of answering questions.

波利卡普正在为他的朋友们设计一个寻宝游戏。他已制作了 $n$ 个任务，对每个任务 $i$，他评估了其趣味性（用整数 $q_i$ 表示）以及完成该任务所需的时间（单位：分钟，记为 $t_i$）。

该游戏的一个有趣特点是：每位参与者都将获得最适合其个人偏好的任务，而任务的选择基于一个交互式问答测验。该测验由若干问题组成，玩家需对每个问题回答“是”或“否”。根据玩家对问题的回答，其将被引导至另一个问题，或直接进入寻宝游戏中某个具体任务。换言之，整个寻宝游戏可建模为一棵二叉树：内部节点代表问题，叶子节点代表任务。

我们已知：在到达最终任务前，玩家每回答一个问题恰好消耗 1 分钟时间。波利卡普知道他的朋友们都很忙，无法在寻宝游戏中花费超过 $T$ 分钟。因此，波利卡普希望从已制作的 $n$ 个任务中选出一部分，为其设计相应的一组问题，并构造一棵二叉树形式的交互式测验，使得无论玩家如何作答，其完成整个寻宝游戏（即回答所有问题并完成最终任务）所花费的总时间均不超过 $T$ 分钟。特别地，该测验可以不包含任何问题，而直接导向某一任务。每个任务最多只能被使用一次（即：给出不同答案序列的玩家必须被分配到不同的任务）。

波利卡普希望所选任务的总“趣味性”值尽可能大。请帮助他确定在满足“任意作答路径下总耗时均不超过 $T$ 分钟”这一约束条件下，所能达到的最大总趣味性值。

The first line contains two integers n and T (1 ≤ n ≤ 1000, 1 ≤ T ≤ 100) — the number of tasks made by Polycarp and the maximum time a quest player should fit into.

Next n lines contain two integers t__i, q__i (1 ≤ t__i ≤ T, 1 ≤ q__i ≤ 1000) each — the time in minutes needed to complete the i-th task and its interest value.

第一行包含两个整数 $n$ 和 $T$（$1 \leq n \leq 1000$，$1 \leq T \leq 100$）—— 分别表示 Polycarp 设计的任务数量以及任务玩家最多可花费的总时间。

接下来的 $n$ 行，每行包含两个整数 $t_i$、$q_i$（$1 \leq t_i \leq T$，$1 \leq q_i \leq 1000$）—— 分别表示完成第 $i$ 个任务所需的时间（单位：分钟）及其趣味值。

Print a single integer — the maximum possible total interest value of all the tasks in the quest.

输出一个整数——任务链中所有任务所能获得的最大总兴趣值。

In the first sample test all the five tasks can be complemented with four questions and joined into one quest.

In the second sample test it is impossible to use all the five tasks, but you can take two of them, the most interesting ones.

In the third sample test the optimal strategy is to include only the second task into the quest.

Here is the picture that illustrates the answers to the sample tests. The blue circles represent the questions, the two arrows that go from every circle represent where a person goes depending on his answer to that question. The tasks are the red ovals.

在第一个样例测试中，全部五个任务都可以通过四个问题来补充，并合并为一个任务链。

在第二个样例测试中，无法使用全部五个任务，但你可以选取其中两个——即最有趣的两个任务。

在第三个样例测试中，最优策略是仅将第二个任务纳入任务链。

下图展示了样例测试的答案示意图：蓝色圆圈表示问题，从每个圆圈出发的两条箭头表示被试者根据对该问题的回答所前往的不同分支。任务用红色椭圆表示。