D. Зачарованный лес
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Marisa приходит собирать грибы в зачарованный лес.

Зачарованный лес может быть представлен $$$n$$$ точками на оси $$$X$$$, пронумерованными от $$$1$$$ до $$$n$$$. Прежде чем Marisa начала собирать грибы, ее подруга Patchouli использовала магию, чтобы узнать изначальное количество грибов в каждой точке, представляемое массивом $$$a_1,a_2,\ldots,a_n$$$.

Marisa может начать в любой точке леса на минуте $$$0$$$. Каждую минуту по заданном порядку происходит следующее:

  • Она перемещается из точки $$$x$$$ в $$$y$$$ ($$$|x-y|\le 1$$$, возможно, $$$y=x$$$).
  • Она собирает все грибы в точке $$$y$$$.
  • В каждой точке леса появляется новый гриб.

Обратите внимание, что она не может собирать грибы в минуту $$$0$$$.

Теперь Marisa хочет узнать максимальное количество грибов, которое она сможет собрать за $$$k$$$ минут.

Входные данные

Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание этих наборов.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$, $$$k$$$ ($$$1 \le n \le 2 \cdot 10 ^ 5$$$, $$$1\le k \le 10^9$$$) — количество позиций с грибами и время, которое есть у Marisa, соответственно.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — изначальное количество грибов в точках $$$1,2,\ldots,n$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10 ^ 5$$$.

Выходные данные

Для каждого набора входных данных выведите максимальное количество грибов, которое Marisa может собрать за $$$k$$$ минут.

Пример
Входные данные
4
5 2
5 6 1 2 3
5 7
5 6 1 2 3
1 2
999999
5 70000
1000000000 1000000000 1000000000 1000000000 1000000000
Выходные данные
12
37
1000000
5000349985
Примечание

В первом наборе входных данных Marisa может начать с $$$x=2$$$. В первую минуту она ходит на $$$x=1$$$ и собирает $$$5$$$ грибов. Количество грибов будет $$$[1,7,2,3,4]$$$. На второй минуте она передвигается на $$$x=2$$$ и собирает $$$7$$$ грибов. Количество грибов будет $$$[2,1,3,4,5]$$$. За $$$2$$$ минуты Marisa собрала $$$12$$$ грибов.

Можно показать, что собрать больше $$$12$$$ грибов невозможно.

Во втором наборе входных данных один из ее возможных путей движения:

$$$2 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$$$

Можно показать, что собрать больше $$$37$$$ грибов невозможно.