food

题目描述:

PKS的餐桌是一个长方形 （即第一盘 和第 \( n \) 盘 不相连）上面放着 \( n \) 盘食物，每一盘食物都有其相应饱食值，PKS必须选择其中的不能重叠的（即一盘食物不能吃多次） \( m \) 段食物来吃（每一段都不能小于 \( 1 \) ）。他太饿了，他希望能得到最大的饱食值。但是食物可能会有负的饱食值，比如吃了会拉肚子。

输入格式:

第一行 2个正整数  \( n \) ， \( m \) 

第二行 \( n \) 个数 为各个食物可以获得的饱食值

输出格式:

一行 为能得到的最大的饱食值

样例输入:

样例1：
5 1
1 2 3 4 5

样例2：
5 2
5 -1 5 -10 5

样例输出:

样例1：
15

样例2：
14

提示:

20%的数据  \( n \le 10^2, m = 1 \) 

20%的数据  \( n \le 10^2, m = 2 \) 

20%的数据  \( n \le 10^5, m = 1 \) 

40%的数据  \( n \le 10^5, m = 2 \) 

时间限制: 1000ms
空间限制: 128MB

---

来源: by pks