← 返回题目列表

Codeforces · 1400/B

B. RPG 主角

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

您正在玩一款 2010 年代的角色扮演游戏。您正计划提高您的锻造技能,因此您需要尽可能多的资源。那么如何获取资源呢?当然是通过偷窃。

你决定抢劫一个城镇的铁匠,并带走了一名追随者。您最多可以携带 $$$p$$$ 单位,而您的追随者则最多可以携带 $$$f$$$ 单位。

在铁匠铺里,你发现了$$$cnt_s$$$剑和$$$cnt_w$$$战斧。每把剑的重量为 $$$s$$$ 单位,每把战斧的重量为 $$$w$$$ 单位。你不在乎拿什么,因为它们都会熔化成一根钢锭。

你和你的追随者可以从商店携带的武器(剑和战斧)的最大数量是多少?

输入

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

每个测试用例的第一行包含两个整数 $$$p$$$ 和 $$$f$$$ ($$$1 \le p, f \le 10^9$$$) - 您和您的追随者的能力。

每个测试用例的第二行包含两个整数 $$$cnt_s$$$ 和 $$$cnt_w$$$ ($$$1 \le cnt_s, cnt_w \le 2 \cdot 10^5$$$) — 商店中剑和战轴的数量。

每个测试用例的第三行包含两个整数 $$$s$$$ 和 $$$w$$$ ($$$1 \le s, w \le 10^9$$$) - 每把剑和每把战斧的重量。

保证所有测试用例中剑的总数和战斧的总数不超过$$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印您和您的追随者可以携带的最大武器数量(剑和战斧)。

示例

输入 #1

3
33 27
6 10
5 6
100 200
10 10
5 5
1 19
1 3
19 5

输出 #1

11
20
3

注意

在第一个测试用例中:

- 你应该拿$$$3$$$剑和$$$3$$$战斧:$$$3 \cdot 5 + 3 \cdot 6 = 33 \le 33$$$
- 和你的追随者 — $$$3$$$ 剑和 $$$2$$$ 战斧:$$$3 \cdot 5 + 2 \cdot 6 = 27 \le 27$$$。

在第二个测试用例中,即使没有追随者的帮助,你也可以拿走所有可用的武器,因为 $$$5 \cdot 10 + 5 \cdot 10 \le 100$$$。

在第三个测试用例中,你不能拿走任何东西,但你的追随者可以拿走 $$$3$$$ 战斧:$$$3 \cdot 5 \le 19$$$。