NO IMAGE

Description

小X同學給小C同學選了N件禮物,決定順序購買並贈送,但作為一個沒有工資沒有零花錢的可憐小朋友,有M位好心的同學伸出了援助之手,然而為了減少最高的借款量,小X同學希望OI競賽的你為他合理規劃,使得他能輕鬆快樂地送出禮物。

Input

第一行輸入兩個用空格隔開的正整數N和M
以下N行每行一個不超過10000正整數,依次表示禮物的價格。

Output

一個整數,即最高借款量。

Sample Input

7 5
100
400
300
100
500
101
400

Sample Output

500

Hint

資料範圍:
30%:n <=10
60%: n<=1000
100%: n<=100000

程式:

var a:array[0..200000]of longint;
n,m,i,l,r,mid,t,s:longint;
begin
readln(n,m);  l:=0;
for i:=1 to n do
begin
readln(a[i]);
if a[i]>l then l:=a[i];
end;
l:=l-1; r:=maxlongint div 2;
while l 1<r do
begin
mid:=(l r) div 2;
t:=0; s:=0;
for i:=1 to n do
begin
if s a[i]>mid then begin inc(t); s:=0; end;
s:=s a[i];
end;
if t>m then l:=mid else r:=mid;
end;
writeln(r);
end.