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\) минут.
Выходные данные
Для каждого набора входных данных выведите максимальное количество грибов, которое Marisa может собрать за \(k\) минут.
Примечание
В первом наборе входных данных 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\) грибов невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|