Монокарп собирается сделать покупку на ровно \(m\) бурлей.
У него есть два типа монет в следующем количестве:
- монеты номиналом \(1\) бурль: \(a_1\) обычных монет и бесконечно много юбилейных монет;
- монеты номиналом \(k\) бурлей: \(a_k\) обычных монет и бесконечно много юбилейных монет.
Монокарп планирует совершить покупку так, чтобы не получить сдачи — суммарный номинал предоставленных монет должен быть ровно \(m\). Он может использовать и обычные, и юбилейные монеты. Однако, он хочет потратить как можно меньше юбилейных монет.
Какое наименьшее суммарное количество юбилейных монет Монокарп может потратить на покупку?
Выходные данные
На каждый набор входных данных выведите одно целое число — наименьшее суммарное количество юбилейных монет, которые Монокарп может потратить на покупку.
Примечание
В первом наборе входных данных нет обычных монет ни одного из типов. Монокарп может использовать \(2\) юбилейные монеты номиналом \(1\) бурль и \(3\) юбилейные монеты номиналом \(3\) (так как \(k=3\)) бурля, чтобы получить суммарно \(11\) бурлей за \(5\) юбилейных монет.
Во втором наборе у Монокарпа очень много обычных монет обоих типов. Он может использовать \(11\) монет номиналом \(1\) бурль, например. Обратите внимание, что Монокарп не обязан минимизировать суммарное количество использованных монет. Таким образом, он использует \(0\) юбилейных монет.
В третьем наборе Монокарп может использовать \(5\) обычных монет номиналом \(1\) бурль и \(1\) обычную монету номиналом \(3\) бурля. Так он получит \(8\) бурлей суммарно, когда ему нужно \(11\). Так что \(1\) юбилейной монеты номиналом \(3\) бурля хватит.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
11 3 0 0
11 3 20 20
11 3 6 1
100000000 2 0 0
|
5
0
1
50000000
|