Вам даны целые числа \(n\) и \(k\).
Назовем массив \(a_1, a_2, \ldots, a_n\) длины \(n\), состоящий из нулей и единиц, хорошим, если для всех целых \(i\) от \(1\) до \(n\) выполняются оба следующих условия:
- среди первых \(i\) элементов \(a\) хотя бы \(\lceil \frac{i}{k} \rceil\) равны \(1\),
- среди последних \(i\) элементов \(a\) хотя бы \(\lceil \frac{i}{k} \rceil\) равны \(1\).
Здесь \(\lceil \frac{i}{k} \rceil\) обозначает результат деления \(i\) на \(k\), округлённый вверх. Например, \(\lceil \frac{6}{3} \rceil = 2\), \(\lceil \frac{11}{5} \rceil = \lceil 2.2 \rceil = 3\) и \(\lceil \frac{7}{4} \rceil = \lceil 1.75 \rceil = 2\).
Найдите наименьшее возможное количество единиц в хорошем массиве.
Выходные данные
Для каждого набора входных данных выведите одно число — наименьшее возможное количество единиц в хорошем массиве.
Можно показать, что при данных ограничениях всегда существует хотя бы один хороший массив.
Примечание
В первом наборе входных данных \(n = 3\) и \(k = 2\):
- Массив \([ \, 1, 0, 1 \, ]\) является хорошим и количество единиц в нём равно \(2\).
- Массивы \([ \, 0, 0, 0 \, ]\), \([ \, 0, 1, 0 \, ]\) и \([ \, 0, 0, 1 \, ]\) не являются хорошими, так как для этих массивов при \(i=1\) не выполняется первое условие.
- Массив \([ \, 1, 0, 0 \, ]\) не является хорошим, так как для него при \(i=1\) не выполняется второе условие.
- Во всех остальных массивах длины \(3\) есть хотя бы \(2\) единицы.
Таким образом, ответ равен \(2\).
Во втором наборе входных данных \(n = 5\) и \(k = 2\):
- Массив \([ \, 1, 1, 0, 0, 1 \, ]\) не является хорошим, так как для него при \(i=3\) не выполняется второе условие.
- Массив \([ \, 1, 0, 1, 0, 1 \, ]\) является хорошим и количество единиц в нём равно \(3\).
- Можно показать, что хорошего массива, содержащего меньше \(3\) единиц, не существует, поэтому ответ равен \(3\).
В третьем наборе входных данных \(n = 9\) и \(k = 3\):
- Массив \([ \, 1, 0, 1, 0, 0, 0, 1, 0, 1 \, ]\) является хорошим и количество единиц в нём равно \(4\).
- Можно показать, что хорошего массива, содержащего меньше \(4\) единиц, не существует, поэтому ответ равен \(4\).
В четвертом наборе входных данных \(n = 7\) и \(k = 1\). Существует единственный хороший массив \([ \, 1, 1, 1, 1, 1, 1, 1\, ]\), поэтому ответ равен \(7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
3 2
5 2
9 3
7 1
10 4
9 5
8 8
|
2
3
4
7
4
3
2
|