CF542F Quest

Polycarp 正在为他的朋友们制作一个任务。他已经制作了 $n$ 个任务，对于每个任务，这个男孩都用一个整数 $q_{i}$ 评估了它的趣味性，并记录了完成该任务所需的时间 $t_{i}$ 分钟。 他的任务设计有一个有趣的特性：每位参与者都应该根据自己的偏好，获得最适合自己的任务。任务的分配是通过一个交互式问答（即 quiz）来完成的，这个问答包含若干个问题。参与者需要用“yes”或“no”来回答这些问题。根据回答的不同，参与者要么继续回答下一个问题，要么分配到任务集合中的一个任务。换句话说，这个任务就是一棵二叉树，树中的结点是问题，叶子结点是任务。 已知，在分到具体任务之前，每答一个问题会花费参与任务的人恰好一分钟。Polycarp 知道他的朋友们都很忙，他们参与任务的总时间不得超过 $T$ 分钟。Polycarp 想从他制作的 $n$ 个任务中选出一些，并为它们设计出相应问题，将它们组装成一个二叉树形式的交互式任务，使得无论参与者如何回答问题，完成整个任务（即回答所有问题和完成最终分配的任务）所需时间都不超过 $T$ 分钟（特别地，任务可以没有提问，直接分配任务）。每个任务只能使用一次（即，回答流程不同的人应该分配到不同的任务）。 Polycarp 想让所有被选中任务的“趣味值”之和最大。请你帮他计算，在保证任务总时长条件下，被选中任务的最大总趣味值。

第一行包含两个整数 $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$ 个任务所需的时间和它的趣味值。

输出一个整数，表示所有被选中任务的最大总趣味值。

在第一个样例中，所有五个任务可以配上四道问题，组成一棵二叉树任务。 在第二个样例中，不能全部选五个任务，但可以选两个趣味性最高的任务。 在第三个样例中，最优策略是只包含第二个任务。 下图描述了样例测试的解法。蓝色圆圈表示问题，每个圆圈有两条分支，表示根据不同回答的去向。红色椭圆表示任务。  由 ChatGPT 5 翻译