← 返回题目列表

Codeforces · 1183/C

C. 电脑游戏

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

Vova 正在玩电脑游戏。游戏中总共有 $$$n$$$ 个回合,Vova 真的很想玩所有回合。他的笔记本电脑电池的初始电量(即游戏开始前的电量)为 $$$k$$$。

在每个回合中,Vova 可以选择要做什么:

- 如果他的笔记本电脑电池的当前电量严格大于$$$a$$$,Vova可以直接玩,然后他的笔记本电脑电池的电量将减少$$$a$$$;
- 如果他的笔记本电脑电池的当前电量严格大于$$$b$$$ ($$$b<a$$$),Vova可以玩他的笔记本电脑并为其充电,然后他的笔记本电脑电池的电量将减少$$$b$$$;
- 如果他的笔记本电脑电池的当前电量同时小于或等于 $$$a$$$ 和 $$$b$$$,则 Vova 无法执行任何操作并输掉游戏。

无论 Vova 转动多少次,笔记本电脑电池的电量始终会减少。

Vova 想要完成游戏(如果在每次 $$$n$$$ 回合后笔记本电脑电池的电量严格大于 $$$0$$$,则 Vova 可以完成游戏)。 Vova 必须精确地玩 $$$n$$$ 个回合。在所有可能的完成游戏的方式中,Vova 希望选择他刚刚玩时的回合数(第一类回合)尽可能最大的一种。 Vova 有可能根本无法完成游戏。

你的任务是找出 Vova 可以玩的最大可能回合数(进行第一种类型的回合)或报告 Vova 无法完成游戏。

您必须回答 $$$q$$$ 独立查询。

输入

输入的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^5$$$) — 查询数。每个查询都由一行表示。

查询中唯一的一行包含四个整数 $$$k、n、a$$$ 和 $$$b$$$ ($$$1 \le k, n \le 10^9, 1 \le b < a \le 10^9$$$) — Vova 笔记本电脑电池的初始电量、游戏的回合数以及相应的值 $$$a$$$ 和 $$$b$$$。

输出

对于每个查询,打印一个整数:如果 Vova 无法完成游戏,则打印一个整数:-1,否则 Vova 可以玩的最大回合数(进行第一个类型的回合)。

示例

输入 #1

6
15 5 3 2
15 5 4 3
15 5 2 1
15 5 5 1
16 7 5 2
20 5 7 3

输出 #1

4
-1
5
2
0
1

注意

在第一个示例查询中,Vova 可以只玩 $$$4$$$ 回合并花费 $$$12$$$ 单位的费用,然后玩一回合并收费并花费 $$$2$$$ 单位。因此电池的剩余电量将为 $$$1$$$。

在第二个示例中,查询 Vova 无法完成游戏,因为即使他在每个回合中玩游戏并为电池充电,笔记本电脑电池的电量在最后一个回合后也将是 $$$0$$$。