var
  n,k,i,e,now,j,m,t,time,left,right,min,p:longint;
  l,r,s,h:array[0..1000000]of longint;
  b:array[0..100000]of boolean;

begin
  assign(input,'peaks.in'); reset(input);
  assign(output,'peaks.out'); rewrite(output);
  readln(n,m);
  for i:=1 to n do
  begin
    read(h[i]);
    s[i]:=s[i-1]+h[i];
  end;
  i:=n;
  min:=maxlongint;
  repeat
    if h[i+1]<h[i] then
    begin
      j:=i-1;
      while h[j]=h[i] do dec(j);
      if h[j]<h[i] then
      begin
        inc(t);
        l[t]:=j+1;
        r[t]:=i;
        for k:=j+1 to i do
        b[i]:=true;
      end;
      i:=j+1;
    end;
    dec(i);
  until i<=0;
  time:=0;
  for e:=2 to t-k+2 do
  begin
    for i:=1 to t do
    begin
      inc(time);
      j:=i+e-1;
      left:=l[i];
      right:=r[j];
      min:=maxlongint;
      for k:=left to right do
      begin
        if h[k]<min then min:=h[k];
        inc(time);
      end;
      left:=k;
      right:=k;
      while h[left]>min do
      begin
        dec(left);
        inc(time);
      end;
      while h[right]>min do
      begin
        inc(right);
        inc(time);
      end;

      p:=0;
      for k:=left to right do
      if (b[k]=b[k+1])and(b[k]) then
      begin
        inc(p);
        inc(time);
      end;
      now:=s[right]-s[left-1]-(right-left+1)*min;
      if t-p<=k then
      begin
        if now<min then min:=now;
      end;
      if time>10000000 then
      begin
        writeln(min);
        close(input);
        close(output);
        halt;
      end;
    end;
  end;
  writeln(min);
  close(input);
  close(output);
end.