站外题求教 网址https://wzoi.cc/s/1/236;

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

输入格式： 第一行 2个正整数 N，M

第二行 N个数 为各个食物可以获得的饱食值

输出格式： 一行 为能得到的最大的饱食值

样例： 输入：

5 1 1 2 3 4 5

输出：

15

提示 20%的数据 n<=100 m=1

20%的数据 n<=100 m=2

20%的数据n<=100000 m=1

40%的数据n<=100000 m=2

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

（另外还有一个样例可自行看网址）