最近，机房出了一个不团结分子：Dr.Weissman。他经常欺骗同学们吃一种“教授糖豆”，使同学们神志不清，殴打他人，砸烂计算机，破坏机房团结。幸运地，一个和谐家认清了Dr.Weissman的本质。机房人民团结在一起，共同对抗Dr.Weissman及“教授糖豆”。
同学们十分具有社会责任感：他们害怕“教授糖豆”流向社会，导致动乱。于是，刚才提到的和谐家身先士卒，为了实验，品尝“教授糖豆”。
每个“教授糖豆”的性质都有所不同。同志们已经研究出每个糖豆对人的影响。具体地，每个糖豆都有一个破坏值，吃掉这颗糖豆后，身先士卒的和谐家会对机房造成一定的破坏，破坏程度为先前累积的破坏值加上本次食用糖豆的破坏值，而且这颗“教授糖豆”的破坏值会加入累积。为了减小实验造成的破坏，同学们准备了几颗“治疗糖豆“，功能是无条件将累积的“破坏值”清零。
由于实验要求，和谐家只能按照给定的顺序吃掉“教授糖豆”，但可以随时吃掉一颗或多颗“治疗糖豆”。
你能帮助和谐家同志尽量减小实验所造成的破坏吗？
输入格式
第一行，两个数，用空格，分隔开，一个n，一个m。（n，m均为正整数。）n表示“教授糖豆”的数目，m表示“治疗糖豆”的数目。
剩余n行，每行1个正整数，表示“教授糖豆”的破坏值。和谐家必须按照给定的顺序，一次一个，吃掉所有“教授糖豆”。
输出格式
一行，一个数，表示实验造成的最小破坏。
样例
样例输入
3 1
1 2 3样例输出
7数据范围与提示
对于100%的数据，1<=n<=100，m<=n 所有破坏值的加和小于10^9。
f[i,j]表示吃第i个破坏豆后吃第j个治疗豆。
先破坏再吃豆，从i开始往前搜第一个吃治疗豆的地方，然后更新
var
f,sum:array[..,..]of int64;
n,m,tot:int64;
i,j,k:longint;
a:array[..]of int64;
function min(x,y:int64):int64;
begin
if x>y then exit(y) else exit(x);
end;
begin
//assign(input,'j.in');reset(input);
//assign(output,'j.out');rewrite(output);
readln(n,m);
for i:= to n do read(a[i]); for i:= to n do
for j:=i to n do
begin
tot:=;
for k:=i to j do
begin
tot:=a[k]+tot;
sum[i,j]:=sum[i,j]+tot;
end;
end;
for i:= to n do//初始化
f[i,]:=sum[,i]; for i:= to n do//刚开始我写的是2，导致f[1,1]的状态为0，WA
for j:= to m do
begin
f[i,j]:=;
for k:= to i do //枚举治疗豆
begin
f[i,j]:=min(f[i,j],f[k,j-]+sum[k+,i]);
end;
end;
writeln(f[n,m]);
close(output);
end.