310614: CF1860B. Fancy Coins

B. Fancy Coinstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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?

Input

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.

Output

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

ExampleInput

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

Output

5
0
1
50000000

Note

In the first testcase, there are no regular coins of either type. Monocarp can use $2$ fancy coins worth $1$ burle and $3$ fancy coins worth $3$ (since $k=3$) burles to get $11$ total burles with $5$ total fancy coins.

In the second testcase, Monocarp has a lot of regular coins of both types. He can use $11$ regular coins worth $1$ burle, for example. Notice that Monocarp doesn't have to minimize the total number of used coins. That way he uses $0$ fancy coins.

In the third testcase, Monocarp can use $5$ regular coins worth $1$ burle and $1$ regular coin worth $3$ burles. That will get him to $8$ total burles when he needs $11$. So, $1$ fancy coin worth $3$ burles is enough.

**题目大意：**

题目描述了一个关于硬币支付的问题。Monocarp想用硬币支付恰好为m burles的费用。他有两种类型的硬币，分别是：

- 价值1 burle的硬币：有a1枚普通硬币和无限多枚花式硬币；
- 价值k burle的硬币：有ak枚普通硬币和无限多枚花式硬币。

Monocarp希望支付时不需要找零——提供的硬币总价值恰好为m burles。他既可以使用普通硬币也可以使用花式硬币，但他希望尽可能少地使用花式硬币。问题是：为了完成支付，Monocarp至少需要使用多少枚花式硬币？

**输入数据格式：**

输入包含多个测试用例。第一行包含一个整数t（1 ≤ t ≤ 3 × 10^4）——测试用例的数量。

每个测试用例占一行，包含四个整数m, k, a1和ak（1 ≤ m ≤ 10^8; 2 ≤ k ≤ 10^8; 0 ≤ a1, ak ≤ 10^8）——分别是购买的成本、第二种硬币的面值以及两种类型普通硬币的数量。

**输出数据格式：**

对于每个测试用例，输出一个整数——Monocarp为了完成支付可以使用到的最少花式硬币数量。

**示例：**

输入：
```
4
11 3 0 0
11 3 20 20
11 3 6 1
100000000 2 0 0
```
输出：
```
5
0
1
50000000
```

**注意：**

在第一个测试用例中，两种类型的普通硬币都没有。Monocarp可以使用2枚价值1 burle的花式硬币和3枚价值3 burles的花式硬币（因为k=3）来总共支付11 burles，并且总共使用了5枚花式硬币。

在第二个测试用例中，Monocarp有大量两种类型的普通硬币。例如，他可以使用11枚价值1 burle的普通硬币。注意，Monocarp不需要最小化使用的硬币总数。这样他就使用了0枚花式硬币。

在第三个测试用例中，Monocarp可以使用5枚价值1 burle的普通硬币和1枚价值3 burles的普通硬币。这样他总共支付了8 burles，而需要支付11 burles。所以，还需要1枚价值3 burles的花式硬币。**题目大意：** 题目描述了一个关于硬币支付的问题。Monocarp想用硬币支付恰好为m burles的费用。他有两种类型的硬币，分别是： - 价值1 burle的硬币：有a1枚普通硬币和无限多枚花式硬币； - 价值k burle的硬币：有ak枚普通硬币和无限多枚花式硬币。 Monocarp希望支付时不需要找零——提供的硬币总价值恰好为m burles。他既可以使用普通硬币也可以使用花式硬币，但他希望尽可能少地使用花式硬币。问题是：为了完成支付，Monocarp至少需要使用多少枚花式硬币？ **输入数据格式：** 输入包含多个测试用例。第一行包含一个整数t（1 ≤ t ≤ 3 × 10^4）——测试用例的数量。 每个测试用例占一行，包含四个整数m, k, a1和ak（1 ≤ m ≤ 10^8; 2 ≤ k ≤ 10^8; 0 ≤ a1, ak ≤ 10^8）——分别是购买的成本、第二种硬币的面值以及两种类型普通硬币的数量。 **输出数据格式：** 对于每个测试用例，输出一个整数——Monocarp为了完成支付可以使用到的最少花式硬币数量。 **示例：** 输入： ``` 4 11 3 0 0 11 3 20 20 11 3 6 1 100000000 2 0 0 ``` 输出： ``` 5 0 1 50000000 ``` **注意：** 在第一个测试用例中，两种类型的普通硬币都没有。Monocarp可以使用2枚价值1 burle的花式硬币和3枚价值3 burles的花式硬币（因为k=3）来总共支付11 burles，并且总共使用了5枚花式硬币。 在第二个测试用例中，Monocarp有大量两种类型的普通硬币。例如，他可以使用11枚价值1 burle的普通硬币。注意，Monocarp不需要最小化使用的硬币总数。这样他就使用了0枚花式硬币。 在第三个测试用例中，Monocarp可以使用5枚价值1 burle的普通硬币和1枚价值3 burles的普通硬币。这样他总共支付了8 burles，而需要支付11 burles。所以，还需要1枚价值3 burles的花式硬币。