← 返回题目列表

Codeforces · 1056/F

F. 写比赛

中文机器翻译题面 查看原题

波利卡普,阿尔卡迪的朋友,准备参加编程竞赛并决定编写一个竞赛。比赛由 $$$n$$$ 个问题组成,持续 $$$T$$$ 分钟。每个问题都由两个正整数 $$$a_i$$$ 和 $$$p_i$$$ 定义 - 其难度和解决方案所获得的分数。

Polycarp 的经验表明,他的技能水平是用正实际值 $$$s$$$ 定义的,并且最初 $$$s=1.0$$$。要解决第 $$$i$$$ 问题,Polycarp 需要 $$$a_i/s$$$ 分钟。

波利卡普喜欢看连续剧,在解决每个问题之前他一定会看一集。波利卡普看完一集后,他的技能会下降$$$10\%$$$,即技能等级$$$s$$$下降到$$$0.9s$$$。每集的观看时间正好为 $$$10$$$ 分钟。当Polycarp决定解决某个问题时,他首先必须观看一集,然后他才开始不间断地解决问题$$$a_i/s$$$分钟,其中$$$s$$$是他当前的技能水平。在计算 $$$a_i/s$$$ 时,不进行舍入,仅将整数值 $$$a_i$$$ 除以实际值 $$$s$$$。

此外,波利卡普可以训练一段时间。如果他训练 $$$t$$$ 分钟,他的技能就会提高 $$$C \cdot t$$$,其中 $$$C$$$ 是某个给定的正实常数。波利卡普只能在解决任何问题之前(以及观看系列赛之前)进行训练。训练的持续时间可以是任意实际值。

波利卡普感兴趣:他在比赛中能得到的最大分数是多少?允许以任何顺序解决问题,而只允许在解决第一个问题之前进行训练。

输入

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

每个测试的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 竞赛中的问题数量。

测试的第二行包含两个实值 $$$C, T$$$ ($$$0 < C < 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$$$ 改变它都不会改变测试答案。

请注意,在 hacks 中你只能使用 $$$tc = 1$$$。

输出

打印 $$$tc$$$ 整数 - 每个测试用例中可能的最高分数。

示例

输入 #1

2
4
1.000 31.000
12 3
20 6
30 1
5 1
3
1.000 30.000
1 10
10 10
20 8

输出 #1

7
20

注意

在第一个示例中,Polycarp 可以获得 $$$7$$$ 的分数,如下所示:

1. 首先他训练 $$$4$$$ 分钟,将 $$$s$$$ 增加到 $$$5$$$ 的值;
2. 然后他决定解决第 $$$4$$$ 问题:他在 $$$10$$$ 分钟内观看一集,他的技能水平下降到 $$$s=5*0.9=4.5$$$,然后他在 $$$5/s=5/4.5$$$ 内解决问题,大约是 $$$1.111$$$ 分钟;
3. 最后,他决定解决 $$$2$$$-nd 问题:他在 $$$10$$$ 分钟内观看一集,他的技能水平下降到 $$$s=4.5*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$$$-st 问题:他在 $$$10$$$ 分钟内观看一集,他的技能下降到 $$$s=5*0.9=4.5$$$,然后他在 $$$1/s=1/4.5$$$ 内解决问题,大约是 $$$0.222$$$ 分钟。
3. 最后,他决定解决 $$$2$$$-nd 问题:他在 $$$10$$$ 分钟内观看一集,他的技能下降到 $$$s=4.5*0.9=4.05$$$,然后他在 $$$10/s=10/4.05$$$ 内解决问题,大约是 $$$2.469$$$ 分钟。

这样,Polycarp 在 $$$4+10+0.222+10+2.469=26.691$$$ 分钟内获得 $$$20$$$ 分数。在 $$$30$$$ 分钟内获得更高分数是不可能的。