Задача 4. Дробные монеты ≡

Условие

В одном государстве в обращении находятся монеты достоинством xy бурлей, где 1 ≤ x < y и xy — несократимая дробь. Например, при y = 5 в ходу монеты достоинством 15, 25, 35 и 45 бурлей, а при y = 6 — монеты 16 и 56.

Хорошим тоном для банковских работников страны является набор требуемой суммы наименьшим количеством монет. Например, если клиент хочет снять сумму 136, ему выдадут пять монет: две монеты достоинством 56 и три монеты достоинством 16.

Определите наименьшее количество монет для набора требуемой денежной суммы py.

Формат входных данных

Первая строка входного файла содержит натуральное число p — числитель требуемой для выдачи суммы, вторая строка содержит натуральное число y — знаменатель достоинств всех монет в стране.

Формат выходных данных

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

1 ≤ p ≤ 10⁵

2 ≤ y ≤ 100

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при y = 2, получат не менее 10 баллов.

Пояснения к примерам

В первом примере дано y = 15. В обращении находятся монеты достоинством 115, 215, 415, 715, 815, 1115, 1315 и 1415.

Для набора суммы 1715 достаточно взять две монеты, например 1315 и 415.

Во втором примере дано y = 2. В обращении находятся только монеты достоинством 12.

Для набора суммы 42 = 21 необходимо взять четыре монеты.

Примеры тестов

17
15

2

4
2

4