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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ p ≤ 105

2 ≤ y ≤ 100

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

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

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
17
15
2
2
4
2
4

0.198s 0.028s 15