Берляндский государственный университет получил файлы обновления для операционной системы. Изначально они установлены только на \(1\)-м компьютере.
Файлы обновлений должны быть скопированы на все \(n\) компьютеров. Компьютеры не подключены к интернету, поэтому единственный способ перенести файлы обновлений с одного компьютера на другой — скопировать их с помощью патч-корда (кабель, соединяющий два компьютера напрямую). Одновременно к компьютеру может быть подключен только один кабель. Это означает, что с любого компьютера, на котором установлены файлы обновления, их можно скопировать на любой другой компьютер всего за один час.
Ваша задача — найти минимальное количество часов, необходимое для копирования файлов обновлений на все \(n\) компьютеров, если в университете есть только \(k\) патч-кордов.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество часов, необходимое для копирования файлов обновлений на все \(n\) компьютеров.
Примечание
Рассмотрим примеры из условия:
- \(n=8\), \(k=3\):
- в течение первого часа мы копируем файлы с компьютера \(1\) на компьютер \(2\);
- в течение второго часа мы копируем файлы с компьютера \(1\) на компьютер \(3\), и с компьютера \(2\) на компьютер \(4\);
- в течение третьего часа мы копируем файлы с компьютера \(1\) на компьютер \(5\), с компьютера \(2\) на компьютер \(6\), и с компьютера \(3\) на компьютер \(7\);
- в течение четвертого часа мы копируем файлы с компьютера \(2\) на компьютер \(8\).
- \(n=6\), \(k=6\):
- в течение первого часа мы копируем файлы с компьютера \(1\) на компьютер \(2\);
- в течение второго часа мы копируем файлы с компьютера \(1\) на компьютер \(3\), и с компьютера \(2\) на компьютер \(4\);
- в течение третьего часа мы копируем файлы с компьютера \(1\) на компьютер \(5\), и с компьютера \(2\) на компьютер \(6\).
- \(n=7\), \(k=1\):
- в течение первого часа мы копируем файлы с компьютера \(1\) на компьютер \(2\);
- в течение второго часа мы копируем файлы с компьютера \(1\) на компьютер \(3\);
- в течение третьего часа мы копируем файлы с компьютера \(1\) на компьютер \(4\);
- в течение четвертого часа мы копируем файлы с компьютера \(4\) на компьютер \(5\);
- в течение пятого часа мы копируем файлы с компьютера \(4\) на компьютер \(6\);
- в течение шестого часа мы копируем файлы с компьютера \(3\) на компьютер \(7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
8 3
6 6
7 1
1 1
|
4
3
6
0
|