题目背景

Special for beginners, ^_^

题目描述

小猫在河边散步，看到河岸上排着很多鱼。每条鱼都有不同的重量，小猫想挑一些鱼吃，但它有一个习惯：每次只能从最左边或者最右边拿一条鱼。 河岸上共有 n 条鱼，重量分别为 a₁,a₂,…,aₙ。

小猫最多只能吃 k 条鱼，并且每次只能从当前剩余鱼的最左边或者最右边拿一条。

请你计算，小猫最多能吃到的鱼的重量总和是多少。

输入格式

第一行两个整数 n 和 k。

第二行 n 个整数，表示每条鱼的重量 aᵢ。

数据范围：

1≤n≤30 1≤k≤n 1≤aᵢ≤10⁹

输出格式

输出一个整数，表示小猫最多能吃到的鱼的重量总和。

样例

5 3
4 7 2 9 5

20

样例解释

一种最优方案是：先拿最左边的 4，再拿最左边的 7，最后拿最右边的 9。

得到的总重量为：

4 + 7 + 9 = 20

因此答案为 20。