← 返回题目列表

Codeforces · 1902/B

B. 获取积分

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

Monocarp 是伯兰州立大学的学生。由于 Berland 教育体系最近发生的变化,Monocarp 只能学习一门科目——编程。

学期由 $$$n$$$ 天组成,为了不被开除,Monocarp 必须在这些 $$$n$$$ 天内获得至少 $$$P$$$ 积分。赚取积分的方式有两种:完成实践任务和参加课程。对于 Monocarp 完成的每项实际任务,他都会获得 $$$t$$$ 积分,对于他参加的每节课,他都会获得 $$$l$$$ 积分。

实际任务在期限内“每周”解锁:第一个任务在 $$$1$$$ 日解锁(可以在 $$$1$$$ 到 $$$n$$$ 的任何一天完成),第二个任务在 $$$8$$$ 日解锁(可以在 $$$8$$$ 到 $$$n$$$ 的任何一天完成),第三个任务在 $$$8$$$ 到 $$$n$$$ 的任何一天解锁天$$$15$$$,依此类推。

每天从$$$1$$$到$$$n$$$,Monocarp可以参加一堂课。每天,Monocarp 都会选择是学习还是休息一整天。当 Monocarp 决定学习时,他会参加一堂课,并且可以完成不超过 $$$2$$$ 的任务,这些任务已经解锁但尚未完成。如果 Monocarp 一整天都在休息,他就会跳过一堂课并忽略任务。

Monocarp 希望尽可能多地休息,即。 e.他想最大限度地增加休息天数。帮他计算一下他最多可以休息多少天!

输入

第一行包含一个整数 $$$tc$$$ ($$$1 \le tc \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的唯一行包含四个整数 $$$n$$$、$$$P$$$、$$$l$$$ 和 $$$t$$$ ($$$1 \le n, l, t \le 10^9$$$; $$$1 \le P \le 10^{18}$$$) — 天数、Monocarp 必须获得的最低总分、参加一堂课的积分和完成一项任务的积分。

对于每个测试用例,如果 Monocarp 参加所有课程并完成所有任务,则可以保证不被开除。

输出

对于每项测试,请打印一个整数 - Monocarp 在不被大学开除的情况下可以休息的最大天数。

示例

输入 #1

5
1 5 5 2
14 3000000000 1000000000 500000000
100 20 1 10
8 120 10 20
42 280 13 37

输出 #1

0
12
99
0
37

注意

在第一个测试用例中,学期持续 $$$1$$$ 天,因此 Monocarp 应在 $$$1$$$ 天参加。由于参加一节课已经获得 $$$5$$$ 积分 ($$$5 \ge P$$$),所以 Monocarp 是否完成任务并不重要。

例如,在第二个测试用例中,Monocarp 可以在 $$$8$$$ 天和 $$$9$$$ 学习:在 $$$8$$$ 天,他将参加一节课,获得 $$$10^9$$$ 分,并完成两项任务,获得另外 $$$5 \cdot 10^8 + 5 \cdot 10^8$$$ 分。而在 $$$9$$$ 那天,他只参加一节课,另外获得 $$$10^9$$$ 积分。

在第三个测试用例中,Monocarp 可以在 $$$42$$$ 天学习:参加课程给他 $$$1$$$ 分,从 $$$6$$$ 可用任务中解决 $$$2$$$ 给他另外 $$$2 \cdot 10$$$ 分。

在第四个测试用例中,Monocarp 必须参加所有课程并完成所有任务才能获得 $$$8 \cdot 10 + 2 \cdot 20 = 120$$$ 积分。

在第五个测试用例中,Monocarp 可以在以下天学习: $$$8$$$ — 一节课以及第一个和第二个任务; $$$15$$$ — 一堂课和第三个任务; $$$22$$$ — 一堂课和第四项任务; $$$29$$$ — 一堂课和第五项任务; $$$36$$$ — 一堂课和第六项任务。