← 返回题目列表

Codeforces · 1860/B

B. 精美硬币

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

Monocarp 将以 $$$m$$$ 的价格进行购买。

他有两种硬币,数量如下:

- 价值 $$$1$$$ burle 的硬币:$$$a_1$$$ 普通硬币和无限多的精美硬币;
- 价值 $$$k$$$ burles 的硬币:$$$a_k$$$ 普通硬币和无限多的精美硬币。

Monocarp 希望以不找零的方式进行购买 — 所提供硬币的总价值恰好为 $$$m$$$。他可以使用普通硬币和花式硬币。然而,他想尽可能少地花花哨的硬币。

他可以用来进行购买的最少总数量是多少?

输入

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

每个测试用例的唯一行包含四个整数 $$$m, k, a_1$$$ 和 $$$a_k$$$ ($$$1 \le m \le 10^8$$$; $$$2 \le k \le 10^8$$$; $$$0 \le a_1, a_k \le 10^8$$$) — 购买成本,价值分别是第二种硬币和两种类型的普通硬币的数量。

输出

对于每个测试用例,打印一个整数 - Monocarp 可用于购买的花式硬币的最小总数。

示例

输入 #1

4
11 3 0 0
11 3 20 20
11 3 6 1
100000000 2 0 0

输出 #1

5
0
1
50000000

注意

在第一个测试用例中,没有任何类型的常规硬币。 Monocarp 可以使用价值 $$$1$$$ burle 的 $$$2$$$ 精美硬币和价值 $$$3$$$ 的 $$$3$$$ 精美硬币(因为 $$$k=3$$$)burles 来获得总 burles $$$11$$$ 和总共 $$$5$$$ 精美硬币。

在第二个测试用例中,Monocarp 有大量两种类型的普通硬币。例如,他可以使用价值 $$$1$$$ burle 的 $$$11$$$ 普通硬币。请注意,Monocarp 不必最小化已用硬币的总数。这样他就可以使用 $$$0$$$ 的精美硬币。

在第三个测试用例中,Monocarp 可以使用价值 $$$1$$$ burle 的 $$$5$$$ 普通硬币和价值 $$$3$$$ burle 的 $$$1$$$ 普通硬币。当他需要 $$$11$$$ 时,这将使他总共获得 $$$8$$$ 的毛刺。因此,价值 $$$3$$$ burles 的 $$$1$$$ 精美硬币就足够了。