У вас есть неограниченное количество монет с номиналами \(1, 2, \ldots, n\). Вы хотите выбрать некоторый набор монет имеющий суммарную стоимость \(S\).
Разрешается чтобы в наборе были монеты имеющие одну и ту же стоимость. Какое минимальное количество монет нужно, чтобы набрать сумму \(S\)?
Выходные данные
Выведите ровно одно целое число — минимальное количество монет, которое нужно чтобы набрать сумму \(S\).
Примечание
Некоторые из способов набрать сумму \(11\) в первом примере с помощью \(3\) монет перечислены ниже:
- \((3, 4, 4)\)
- \((2, 4, 5)\)
- \((1, 5, 5)\)
- \((3, 3, 5)\)
Набрать сумму \(11\) меньше чем за \(3\) монеты нельзя.
Во втором примере некоторые из способов набрать \(16\) используя \(3\) монеты такие:
- \((5, 5, 6)\)
- \((4, 6, 6)\)
Набрать сумму \(16\) меньше чем за \(3\) монеты нельзя.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 11
|
3
|
|
2
|
6 16
|
3
|