Вы работаете администратором в общежитии, состоящем из \(n\) комнат, расположенных в ряд вдоль коридора. Комнаты пронумерованы слева направо от \(1\) до \(n\).
Вы хотите подключить все \(n\) комнат к интернету.
Каждая из комнат может быть подключена к интернету кабелем напрямую, стоимость подключения \(i\)-й комнаты равна \(i\) монет.
В некоторых комнатах также есть место для установки роутера. Стоимость установки роутера в \(i\)-й комнате также равна \(i\) монет. Вы не можете поставить роутер в комнате, в которой нет места для его установки. Когда вы ставите роутер в комнате \(i\), вы подключаете все комнаты с номерами от \(max(1,~i - k)\) до \(min(n,~i + k)\) включительно к интернету, где \(k\) — это радиус действия роутера. Значение \(k\) одинаково для всех роутеров.
Определите минимальную стоимость подключения всех \(n\) комнат к интернету. Считайте, что количество комнат, в которые можно установить роутеры, не превосходит количества роутеров, которые у вас есть.
Выходные данные
Выведите одно целое число — минимальную стоимость подключения всех \(n\) комнат к интернету.
Примечание
В первом примере достаточно установить роутер в комнату \(3\), тогда все комнаты будут подключены к интернету. Стоимость подключения равна \(3\).
Во втором примере нельзя устанавливать роутеры ни в одну из комнат, поэтому все комнаты нужно подключать напрямую кабелем. Таким образом, стоимость подключения всех комнат равна \(1 + 2 + 3 + 4 + 5 + 6 = 21\).
В третьем примере комнату \(1\) нужно подключить напрямую кабелем, а в комнату \(3\) установить роутер. Таким образом, стоимость подключения всех комнат равна \(1 + 3 = 4\).
В четвертом примере нужно установить роутеры в комнаты \(5\) и \(10\). Тогда все комнаты будут подключены к интернету. Стоимость подключения равна \(5 + 10 = 15\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
00100
|
3
|
|
2
|
6 1
000000
|
21
|
|
3
|
4 1
0011
|
4
|
|
4
|
12 6
000010000100
|
15
|