Петя вернулся из школы и понял, что забыл купить хлеб. А ещё он понял, что действовать надо достаточно быстро: через $$$n$$$ минут начинается телетрансляция важного матча его любимой футбольной команды.
Путь от дома Пети до пекарни занимает $$$t$$$ минут, и столько же ему потребуется на обратную дорогу. На покупку хлеба уйдёт одна минута. Гарантируется, что $$$2 \cdot t + 1 \le n$$$.
Петя уже был готов отправиться за хлебом, но начал накрапывать дождик. Согласно прогнозу погоды дождь будет идти в ближайшие $$$n$$$ минут, и для каждой $$$j$$$-й минуты известно количество осадков $$$d_j$$$, которое выпадет в эту минуту.
Петя хочет, чтобы суммарное количество осадков, которое выпадет, пока он будет идти по улице, было минимально возможным.
Петя может повременить с выходом из дома, может немного подождать в пекарне и не уходить оттуда сразу после совершения покупки. Главное — он должен вернуться домой не позднее, чем через $$$n$$$ минут. Ваша задача — определить минимально возможное суммарное количество осадков, которое выпадет, пока Петя будет находиться на улице.
В первой строке содержится целое число $$$n$$$ $$$(n \le 3 \cdot 10^5)$$$ — максимальное время, спустя которое Петя должен быть дома.
Во второй строке содержится целое число $$$t$$$ ($$$t\ge 1$$$, $$$2t+1\le n$$$) — время, которое необходимо Пете, чтобы дойти от дома до пекарни или обратно.
В каждой из следующих $$$n$$$ строк содержится по одному целому числу $$$d_j$$$ $$$1 \le d_j \le 10^3, \, j = 1, 2, \ldots, n)$$$ — количество осадков, которое выпадет в $$$j$$$-ю минуту.
Выведите целое число — минимально возможное суммарное количество осадков, которое выпадет, пока Петя будет идти по улице.
Решения, верно работающие при $$$n \le 100$$$, будут оцениваться в 40 баллов.
184521421113211412312162
15
В примере из условия Пете следует выйти из дома в 3-ю минуту. Количество осадков, которое выпадет за время его нахождения на улице, составит $$$1 + 4 + 2 + 1 = 8$$$. В 7-ю он совершит покупку, после чего, начиная с 8-й минуты, он может отправиться обратно.
Наилучшим решением для него будет подождать до 13-й минуты: если он выйдет из пекарни в этот момент, то количество осадков, которое выпадет за время его нахождения на улице, составит $$$3 + 1 + 2 + 1 = 7$$$.
Суммарное количество осадков будет равно $$$15$$$. Можно проверить, что в других случаях количество осадков будет больше.
