CF1860B Fancy Coins

Monocarp 计划进行一次恰好花费 $m$ burles 的购物。 他有两种面值的硬币，数量如下： - 面值为 $1$ burle 的硬币：有 $a_1$ 枚普通硬币，以及无限多的“花式”硬币； - 面值为 $k$ burles 的硬币：有 $a_k$ 枚普通硬币，以及无限多的“花式”硬币。 Monocarp 想要用硬币恰好支付 $m$ burles，不找零。他可以同时使用普通硬币和花式硬币。然而，他希望使用的花式硬币总数尽可能少。 请问他最少需要使用多少枚花式硬币才能完成支付？

第一行包含一个整数 $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 最少需要使用的花式硬币总数。

在第一个测试用例中，两种普通硬币都没有。Monocarp 可以使用 $2$ 枚面值为 $1$ burle 的花式硬币和 $3$ 枚面值为 $3$（因为 $k=3$）burles 的花式硬币，总共 $5$ 枚花式硬币，恰好支付 $11$ burles。 在第二个测试用例中，Monocarp 有很多两种普通硬币。例如，他可以只用 $11$ 枚面值为 $1$ burle 的普通硬币。注意，Monocarp 不需要最小化硬币总数，只需要最小化花式硬币数量。这样他可以完全不用花式硬币。 在第三个测试用例中，Monocarp 可以用 $5$ 枚面值为 $1$ burle 的普通硬币和 $1$ 枚面值为 $3$ burles 的普通硬币，这样共支付 $8$ burles，还差 $3$ burles。因此，只需再用 $1$ 枚面值为 $3$ burles 的花式硬币即可。 由 ChatGPT 4.1 翻译