CF1056F.Write The Contest

Polycarp, Arkady's friend, prepares to the programming competition and decides to write a contest. The contest consists of $n$ problems and lasts for $T$ minutes. Each of the problems is defined by two positive integers $a_i$ and $p_i$ — its difficulty and the score awarded by its solution.

Polycarp's experience suggests that his skill level is defined with positive real value $s$, and initially $s=1.0$. To solve the $i$-th problem Polycarp needs $a_i/s$ minutes.

Polycarp loves to watch series, and before solving each of the problems he will definitely watch one episode. After Polycarp watches an episode, his skill decreases by $10\%$, that is skill level $s$ decreases to $0.9s$. Each episode takes exactly $10$ minutes to watch. When Polycarp decides to solve some problem, he firstly has to watch one episode, and only then he starts solving the problem without breaks for $a_i/s$ minutes, where $s$ is his current skill level. In calculation of $a_i/s$ no rounding is performed, only division of integer value $a_i$ by real value $s$ happens.

Also, Polycarp can train for some time. If he trains for $t$ minutes, he increases his skill by $C \cdot t$, where $C$ is some given positive real constant. Polycarp can train only before solving any problem (and before watching series). Duration of the training can be arbitrary real value.

Polycarp is interested: what is the largest score he can get in the contest? It is allowed to solve problems in any order, while training is only allowed before solving the first problem.

Polycarp（Arkady 的朋友）正在为一场编程竞赛做准备，并决定举办一场比赛。该比赛包含 $n$ 道题目，总时长为 $T$ 分钟。每道题目 $i$ 由两个正整数 $a_i$ 和 $p_i$ 描述——分别表示其难度和解出后获得的分数。

根据 Polycarp 的经验，他的技能水平由一个正实数 $s$ 表示，初始时 $s = 1.0$。要解出第 $i$ 道题，Polycarp 需要 $\frac{a_i}{s}$ 分钟。

Polycarp 热爱看剧，在解决每一道题之前，他一定会先看一集。每看完一集后，他的技能水平会下降 $10\%$，即技能值 $s$ 变为 $0.9s$。每集电视剧恰好耗时 $10$ 分钟。当 Polycarp 决定解某道题时，他必须首先观看一集电视剧，然后才开始连续解题，解题耗时为 $\frac{a_i}{s}$ 分钟，其中 $s$ 是他当前的技能水平。在计算 $\frac{a_i}{s}$ 时不做任何舍入，仅执行整数 $a_i$ 除以实数 $s$ 的运算。

此外，Polycarp 还可以进行训练。若他训练 $t$ 分钟，则其技能水平将提升 $C \cdot t$，其中 $C$ 是给定的某个正实常数。Polycarp 只能在解任何题目之前（且在看剧之前）进行训练。训练时长可以是任意非负实数。

Polycarp 想知道：他在本次比赛中最多能获得多少分？题目可以按任意顺序求解，但训练仅允许在解第一道题之前进行。

The first line contains one integer $tc$ ($1 \le tc \le 20$) — the number of test cases. Then $tc$ test cases follow.

The first line of each test contains one integer $n$ ($1 \le n \le 100$) — the number of problems in the contest.

The second line of the test contains two real values $C, T$ ($0 \lt C \lt 10$, $0 \le T \le 2 \cdot 10^5$), where $C$ defines the efficiency of the training and $T$ is the duration of the contest in minutes. Value $C, T$ are given exactly with three digits after the decimal point.

Each of the next $n$ lines of the test contain characteristics of the corresponding problem: two integers $a_i, p_i$ ($1 \le a_i \le 10^4$, $1 \le p_i \le 10$) — the difficulty and the score of the problem.

It is guaranteed that the value of $T$ is such that changing it by the $0.001$ in any direction will not change the test answer.

Please note that in hacks you can only use $tc = 1$.

第一行包含一个整数 $tc$（$1 \le tc \le 20$）—— 测试用例的数量。随后是 $tc$ 个测试用例。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 100$）—— 比赛中问题的数量。

每个测试用例的第二行包含两个实数 $C, T$（$0 \lt C \lt 10$，$0 \le T \le 2 \cdot 10^5$），其中 $C$ 表示训练效率，$T$ 表示比赛持续时间（单位：分钟）。$C$ 和 $T$ 均精确给出至小数点后三位。

接下来的 $n$ 行每行描述对应问题的特征：两个整数 $a_i, p_i$（$1 \le a_i \le 10^4$，$1 \le p_i \le 10$）—— 分别为该问题的难度和分值。

保证 $T$ 的取值满足：将其在任意方向上改变 $0.001$，均不会影响该测试用例的答案。

请注意，在 hack 中仅允许使用 $tc = 1$。

Print $tc$ integers — the maximum possible score in each test case.

输出 $tc$ 个整数——每个测试用例中可能获得的最高分数。

In the first example, Polycarp can get score of $7$ as follows:

1. Firstly he trains for $4$ minutes, increasing $s$ to the value of $5$;
2. Then he decides to solve $4$-th problem: he watches one episode in $10$ minutes, his skill level decreases to $s=5*0.9=4.5$ and then he solves the problem in $5/s=5/4.5$, which is roughly $1.111$ minutes;
3. Finally, he decides to solve $2$-nd problem: he watches one episode in $10$ minutes, his skill level decreases to $s=4.5*0.9=4.05$ and then he solves the problem in $20/s=20/4.05$, which is roughly $4.938$ minutes.

This way, Polycarp uses roughly $4+10+1.111+10+4.938=30.049$ minutes, to get score of $7$ points. It is not possible to achieve larger score in $31$ minutes.

In the second example, Polycarp can get $20$ points as follows:

1. Firstly he trains for $4$ minutes, increasing $s$ to the value of $5$;
2. Then he decides to solve $1$-st problem: he watches one episode in $10$ minutes, his skill decreases to $s=5*0.9=4.5$ and then he solves problem in $1/s=1/4.5$, which is roughly $0.222$ minutes.
3. Finally, he decides to solve $2$-nd problem: he watches one episode in $10$ minutes, his skill decreases to $s=4.5*0.9=4.05$ and then he solves the problem in $10/s=10/4.05$, which is roughly $2.469$ minutes.

This way, Polycarp gets score of $20$ in $4+10+0.222+10+2.469=26.691$ minutes. It is not possible to achieve larger score in $30$ minutes.

在第一个例子中，Polycarp 可以按如下方式获得 $7$ 分：

1. 首先，他训练 $4$ 分钟，将技能值 $s$ 提升至 $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$ 分钟，将技能值 $s$ 提升至 $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$ 分钟内无法获得更高分数。