A16108 | $Fancy Coins$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

Monocarp is going to make a purchase with cost of exactly $m$ burles. He has two types of coins, in the following quantities: - coins worth $1$ burle: $a_1$ regular coins and infinitely many fancy coins; - coins worth $k$ burles: $a_k$ regular coins and infinitely many fancy coins. Monocarp wants to make his purchase in such a way that there's no change — the total worth of provided coins is exactly $m$ . He can use both regular and fancy coins. However, he wants to spend as little fancy coins as possible. What's the smallest total number of fancy coins he can use to make a purchase?

The first line contains a single integer $t$ ( $1 \le t \le 3 \cdot 10^4$ ) — the number of testcases. The only line of each testcase contains four integers $m, k, a_1$ and $a_k$ ( $1 \le m \le 10^8$ ; $2 \le k \le 10^8$ ; $0 \le a_1, a_k \le 10^8$ ) — the cost of the purchase, the worth of the second type of coin and the amounts of regular coins of both types, respectively.

For each testcase, print a single integer — the smallest total number of fancy coins Monocarp can use to make a purchase.

输入 #1

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

输出 #1

C++ 编辑器

输入

输出