Quest

题意翻译

有 $n$ 个任务，每个任务有两个值：$t_i$ 和 $q_i$。 你需要构造一个二叉树，满足： 1. 每个非叶子节点都有两个儿子。 2. 每个叶子节点都对应一个任务，且两两不同。（不一定所有的任务都要被对应） 3. 所有叶子节点都满足 它到根的距离加上 $t_i$ 不超过 $T$。 这样的一个二叉树的权值是所有叶子节点的 $q_i$ 之和。 求最大权值。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

5 5
1 1
1 1
2 2
3 3
4 4

输出样例 #1

11

输入样例 #2

5 5
4 1
4 2
4 3
4 4
4 5

输出样例 #2

9

输入样例 #3

2 2
1 1
2 10

输出样例 #3

10

说明

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.