记录编号	15256	评测结果	AAAAAAAAAA
题目名称	[USACO Mar07] 月度花费	最终得分	100
用户昵称	maxiem	是否通过	通过
代码语言	Pascal	运行时间	0.116 s
提交时间	2009-11-11 12:39:41	内存使用	0.30 MiB

program expense;
var
  money:array [1..100000] of integer;
  a,b,tmp:int64;
  i,n,m:longint;
function check(num:int64):boolean;
var
  k,i:longint;
  sum:int64;
begin
  sum:=0;k:=m;
  for i:=1 to n do begin
    sum:=sum+money[i];
    if sum>num then begin
      dec(k);
      sum:=money[i];
      if sum>num then exit(false);
    end;
  end;
  dec(k);
  if k<0 then exit (false) else exit (true);
end;
begin
  assign (input,'expense.in');
  reset (input);
  readln (n,m);b:=0;
  for i:=1 to n do begin
    readln (money[i]);
    b:=b+money[i];
  end;
  close (input);
  assign (output,'expense.out');
  rewrite (output);
  a:=1;
  while a<b do begin
    tmp:=(a+b) div 2;
    if check(tmp) then b:=tmp else a:=tmp+1;
  end;
  writeln (a);
  close (output);
end.