这显然是一道环形dp的题目
处理环形我们都是要转化为线性来做
一般有这么两种方法处理
复制一段到最后 （比如说noip的能量项链）
考查环形对dp的影响然后分类讨论（比如bzoj1040）
这道题我们用第二种方法更好
先不考虑环的问题
设f[i,j,0/1]表示到第i段时间用了j段睡觉且当前（0表示为入睡，1表示已入睡）所带来的最大效用值
不难写出对应的转移方程；
然后我们分析环，不难发现，环的影响仅仅在第一段时间入睡是否能拿到对应的效用值
就是到最后我一直睡，睡到1,1的效用值是可以拿到的，而这是线性所拿不到的
因此我们再做一遍dp，强制第n段时间入睡即可，最终几种情况取最大值即可
const inf=-2147483647;
var f,g:array[0..1,0..4000,0..1] of longint;
a:array[0..4010] of longint;
n,k,i,j,t:longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
begin
readln(n,k);
for i:=1 to n do
readln(a[i]);
for i:=0 to k do
for j:=0 to 1 do
begin
f[0,i,j]:=inf;
g[0,i,j]:=inf;
end;
f[0,0,0]:=0;
f[0,1,1]:=0;
g[0,1,1]:=0;
t:=0;
for i:=2 to n do
begin
t:=1-t;
for j:=0 to k do
begin
f[t,j,0]:=max(f[1-t,j,0],f[1-t,j,1]);
g[t,j,0]:=max(g[1-t,j,0],g[1-t,j,1]);
if j>0 then
begin
f[t,j,1]:=max(f[1-t,j-1,1]+a[i],f[1-t,j-1,0]);
g[t,j,1]:=max(g[1-t,j-1,1]+a[i],g[1-t,j-1,0]);
end
else begin
f[t,j,1]:=inf;
g[t,j,1]:=inf;
end;
end;
end;
writeln(max(max(f[t,k,0],f[t,k,1]),g[t,k,1]+a[1]));
end.