program yueduhuafei;
var
  n,m,i,j,k,t,min:longint;
  f:array[1..1000,1..1000]of longint;
  a:array[1..1000] of integer;
  he:array[1..1000,1..1000]of integer;
function max(w,b:longint):longint;
begin
if w>b then
  max:=w
else
  max:=b
end;
begin
  assign(input,'expense.in');
  reset (input);
  assign (output,'expense.out');
  rewrite (output);
  readln (n,m);
  for i:=1 to n do
  begin
    readln (a[i]);
    t:=t+a[i];
    f[i,1]:=t
  end;
  for i:=1 to n do
    he[i,i]:=a[i];
  for i:=1 to n-1 do
    for j:=i+1 to n do
      he[i,j]:=he[i,j-1]+a[j];
  for i:=1 to m do
    f[1,i]:=maxlongint;
  f[1,1]:=a[1];
  for i:=2 to n do
    for j:=2 to m do
      if i>=j then
      begin
        min:=maxlongint;
        for k:=i-1 downto 1 do
          if max(f[k,j-1],he[k+1,i])<min then
            if k>=j-1 then
              min:=max(f[k,j-1],he[k+1,i]);
        f[i,j]:=min
      end
      else
        f[i,j]:=maxlongint;
  writeln (f[n,m]);
  close (input);
  close (output)
end.