На стол в ряд выложены карточки, на каждой карточке написано натуральное число. За один ход разрешается взять карточку либо с левого, либо с правого конца ряда. Всего можно сделать k ходов. Итоговый счет равен сумме чисел на выбранных карточках. Определите, какой максимальный счет можно получить по итогам игры.

В первой строке записано число карточек n (1≤n≤10⁵).
Во второй строке записано число ходов k (1≤k≤n).
В третьей строке через пробел даны числа, записанные на карточках. i-е по счету число записано на i-й слева карточке. Все числа натуральные и не превосходят 10⁴.

Выведите единственное число —- максимальную сумму очков, которую можно набрать, сделав k ходов.