CF1056F Write The Contest

Polycarp，Arkady 的朋友，正在为编程比赛做准备，并决定自己出一场比赛。比赛包含 $n$ 道题目，持续 $T$ 分钟。每道题目由两个正整数 $a_i$ 和 $p_i$ 描述，分别表示其难度和解出该题可获得的分数。 根据 Polycarp 的经验，他的能力值用一个正实数 $s$ 表示，初始时 $s=1.0$。要解第 $i$ 道题，Polycarp 需要花费 $a_i/s$ 分钟。 Polycarp 喜欢追剧，在解每道题之前，他一定会看一集剧。每看一集剧，他的能力会下降 $10\%$，即能力值 $s$ 变为 $0.9s$。每集剧正好需要 $10$ 分钟。当 Polycarp 决定解某道题时，他首先要看一集剧，然后才能连续解题 $a_i/s$ 分钟（此处 $s$ 为当前能力值）。在计算 $a_i/s$ 时，不进行任何取整，仅做整数 $a_i$ 与实数 $s$ 的除法。 此外，Polycarp 还可以进行训练。如果他训练 $t$ 分钟，他的能力值会提升 $C \cdot t$，其中 $C$ 是给定的正实数常数。Polycarp 只能在解第一道题之前（且在看剧之前）进行训练，训练时间 $t$ 可以为任意实数。 Polycarp 想知道，在比赛时间内，他最多能获得多少分？题目可以按任意顺序解答，但训练只能在解第一道题之前进行。

第一行包含一个整数 $tc$（$1 \le tc \le 20$），表示测试用例的数量。接下来是 $tc$ 组测试数据。 每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 100$），表示比赛的题目数量。 第二行包含两个实数 $C, T$（$0 < C < 10$，$0 \le T \le 2 \times 10^5$），$C$ 表示训练效率，$T$ 表示比赛总时长（单位：分钟）。$C$ 和 $T$ 均精确到小数点后三位。 接下来的 $n$ 行，每行包含两个整数 $a_i, p_i$（$1 \le a_i \le 10^4$，$1 \le p_i \le 10$），分别表示第 $i$ 道题的难度和分数。 保证 $T$ 的取值满足：将其增加或减少 $0.001$ 都不会改变本题的答案。 请注意，在 hack 数据中只能使用 $tc = 1$。

输出 $tc$ 个整数，每行一个，表示每组测试数据中 Polycarp 能获得的最大分数。

在第一个样例中，Polycarp 可以获得 $7$ 分，具体如下： 1. 首先他训练 $4$ 分钟，将能力值提升到 $5$； 2. 然后他选择先解第 $4$ 题：先花 $10$ 分钟看一集剧，能力值降为 $s=5 \times 0.9=4.5$，然后用 $5/s=5/4.5$ 分钟解题，约为 $1.111$ 分钟； 3. 最后他解第 $2$ 题：再花 $10$ 分钟看一集剧，能力值降为 $s=4.5 \times 0.9=4.05$，然后用 $20/s=20/4.05$ 分钟解题，约为 $4.938$ 分钟。 这样，Polycarp 总共用时约 $4+10+1.111+10+4.938=30.049$ 分钟，获得 $7$ 分。在 $31$ 分钟内无法获得更高分数。 在第二个样例中，Polycarp 可以获得 $20$ 分，具体如下： 1. 首先他训练 $4$ 分钟，将能力值提升到 $5$； 2. 然后他选择先解第 $1$ 题：先花 $10$ 分钟看一集剧，能力值降为 $s=5 \times 0.9=4.5$，然后用 $1/s=1/4.5$ 分钟解题，约为 $0.222$ 分钟； 3. 最后他解第 $2$ 题：再花 $10$ 分钟看一集剧，能力值降为 $s=4.5 \times 0.9=4.05$，然后用 $10/s=10/4.05$ 分钟解题，约为 $2.469$ 分钟。 这样，Polycarp 总共用时约 $4+10+0.222+10+2.469=26.691$ 分钟，获得 $20$ 分。在 $30$ 分钟内无法获得更高分数。 由 ChatGPT 4.1 翻译