Задан массив \(a_1, a_2, \dots, a_n\), состоящий из \(n\) положительных целых чисел.
Изначально вы находитесь в позиции \(1\), и ваше количество очков равно \(a_1\). Можно совершать два типа шагов:
- шаг вправо — перейти из текущей позиции \(x\) в \(x+1\) и получить \(a_{x+1}\) очков. Этот шаг можно делать только если \(x<n\).
- шаг влево — перейти из текущей позиции \(x\) в \(x-1\) и получить \(a_{x-1}\) очков. Этот шаг можно делать только если \(x>1\). Также нельзя совершать два или более шагов влево подряд.
Вам требуется совершить ровно \(k\) шагов. Не более \(z\) из них могут быть шагами влево.
Какое наибольшее количество очков можно получить?
Выходные данные
Выведите \(t\) целых чисел — для каждого набора входных данных выведите наибольшее количество очков, которое можно получить, если требуется сделать ровно \(k\) шагов, не более \(z\) из них могут быть шагами влево и не должно быть двух шагов влево подряд.
Примечание
В первом наборе входных данных не разрешается ходить влево вообще. Поэтому делаем четыре шага вправо и получаем \(a_1 + a_2 + a_3 + a_4 + a_5\) очков.
Во втором наборе входных данных можно сделать один ход влево. Тогда сделаем такие шаги: вправо, вправо, влево, вправо. Получится \(a_1 + a_2 + a_3 + a_2 + a_3\) очков.
В третьем наборе входных данных можно ходить влево до четырех раз, но это все равно не оптимально, можем просто сделать четыре шага вправо и получить \(a_1 + a_2 + a_3 + a_4 + a_5\) очков.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5 4 0
1 5 4 3 2
5 4 1
1 5 4 3 2
5 4 4
10 20 30 40 50
10 7 3
4 6 8 2 9 9 7 4 10 9
|
15
19
150
56
|