program energoencefalita;
type vect=array[1..5000] of longint;
var a,b:vect;
    f,g:text;
    gr,tot,n,i,j,p,w,greu,cost:longint;
begin
assign(f,'energii.in'); reset(f);
assign(g,'energii.out'); rewrite(g);
read(f,n);
read(f,tot);
read(f,greu,cost);
for i:= 1 to tot do begin a[i]:=-1; b[i]:=-1 end;
if greu<tot then for i:=1 to greu do a[i]:=cost
            else for i:=1 to tot do a[i]:=cost;
for i:=1 to n-1 do begin
    read(f,greu,cost);
    if greu<tot then begin
       for j:=1 to greu do
          if (a[j]<cost) and (a[j]>-1) then b[j]:=a[j]
                                      else b[j]:=cost;
            p:=greu+1;  w:=1;
            while (p<=tot) and (a[w]>-1) do begin
                  if (cost+a[w]>a[p]) and (a[p]>-1) then  b[p]:=a[p]
                                    else   b[p]:=cost+a[w];
                  inc(p); inc(w);
                 end;
                 end
          else
          for j:=1 to tot do
                 if (a[j]<cost) and (a[j]>0) then b[j]:=a[j]
                                      else b[j]:=cost;
      a:=b;
      end;
if a[tot]=0 then writeln(g,-1)
            else writeln(g,a[tot]);
close(f); close(g);
end.