На стол в ряд выложены карточки, на каждой карточке написано натуральное число. За один ход разрешается взять карточку либо с левого, либо с правого конца ряда. Всего можно сделать k ходов. Итоговый счет равен сумме чисел на выбранных карточках. Определите, какой максимальный счет можно получить по итогам игры.
В первой строке записано число карточек n (1≤n≤105).
Во второй строке записано число ходов k (1≤k≤n).
В третьей строке через пробел даны числа, записанные на карточках. i-е по счету число записано на i-й слева карточке. Все числа натуральные и не превосходят 104.
Выведите единственное число —- максимальную сумму очков, которую можно набрать, сделав k ходов.
|
7 3 5 8 2 1 3 4 11 |
24 |
|
5 5 1 2 3 4 5 |
15 |
|
7 4 1 1 9 2 2 2 6 |
17 |