type Tnum=array[1..17000] of longint;
var a,b:text;
	l,i,j,maxSum,k,n,mx:longint;
	t,s:Tnum;
	
function min(a,b:longint):longint;
begin
	if a>b then min:=b else min:=a;
end;

function calc(maxSum:longint):boolean;
begin
	i:=1;
	j:=1;
	while (i<=k) and (j<=n) do
	begin
		if s[i]+t[j]<=maxSum then
		begin
		s[i]:=s[i]+t[j];
		j:=j+1;
		end else i:=i+1;
	end;
	for l:=1 to i do
	s[l]:=0;
	
	if (i<=n) and (j>n) then calc:=true else calc:=false;
	
end;

function bs(s,f:longint):longint;
var mid:longint;
begin
	bs:=99999999;
	if s<=f then
	begin
		mid:=(s+f) div 2;
		if (calc(mid)=true) then 
			bs:=min(mid,bs(s,mid-1)) else 
			bs:=bs(mid+1,f);
			
	end;
end;

begin
assign(a,'transport.in');
reset(a);
assign(b,'transport.out');
rewrite(b);
read(a,n,k);
maxSum:=0;

for l:=1 to n do
begin
	read(a,t[l]);
	maxSum:=maxSum+t[l];
end;

mx:=-1;
for l:=1 to n do
	if t[l]>mx then mx:=t[l];

writeln(b,bs(mx,maxSum));

close(a);
close(b);
end.