program train;
var
 a,b:array[1..100]of integer;
 n,m,i,j,k,head,tail,max,x:integer;
 g:array[1..100]of boolean;
 f:text;

procedure find;
begin
if max<x then max:=x;
end;
procedure go1(t:integer);
var i,j,k:integer;
begin
x:=x+1;g[t]:=false;
find;
for i:=1 to n do
 begin
 if (b[t]<=a[i])and g[i] then
      begin go1(i);end;
 end;
g[t]:=true;x:=x-1;

end;

procedure go2(t1,t2:integer);
var i,j,k:integer;
begin
x:=x+2;
g[t1]:=false;g[t2]:=false;
find;
for i:=1 to n do
  for j:=1 to n do
   if i<>j then
     begin
   if (b[t1]<=a[t1])and(b[t2]<=a[t2])and(g[t1])and(g[t2])
     then  begin go2(i,j);end
  else
    begin
     if (b[t1]<=a[t1])and(g[t1]) then go1(i);
     if (b[t2]<=a[t2])and(g[t2]) then go1(j);
    end;
     end;
g[t1]:=true;g[t2]:=true;
end;

procedure go3(t1,t2,t3:integer);
var i,j,k:integer;
begin
x:=x+3;
g[t1]:=false;g[t2]:=false;g[t3]:=false;
find;
for i:=1 to n do
 for j:=1 to n do
   for k:=1 to n do
     if (i<>j)and(i<>k)and(k<>j)and(g[t1])and(g[t2])and(g[t3])
         and(b[t1]<=a[t1])and(b[t2]<=a[t2])and(b[t3]<=a[t3])
         then begin go3(i,j,k); end
     else
       begin
       if (i<>j)and(b[t1]<=a[t1])and(b[t2]<=a[t2])and(g[t1])and(g[t2])
            then  begin go2(i,j);end;
       if (i<>k)and(b[t1]<=a[t1])and(b[t3]<=a[t3])and(g[t1])and(g[t3])
             then  begin go2(i,k);end;
       if (k<>j)and(b[t3]<=a[t3])and(b[t2]<=a[t2])and(g[t3])and(g[t2])
              then  begin go2(j,k);end;
       if (b[t1]<=a[t1])and(g[t1]) then go1(i);
       if (b[t2]<=a[t2])and(g[t2]) then go1(j);
       if (b[t3]<=a[t3])and(g[t3]) then go1(k);
       end;



g[t1]:=true;g[t2]:=true;g[t3]:=true;
end;


Begin
assign(f,'train.in');reset(f);
readln(f,n,m);
for i:=1 to n do readln(f,a[i],b[i]);
for i:=1 to n do g[i]:=true;
close(f);
max:=0;
if m=1 then
  for i:=1 to n do begin x:=0;go1(i);end;
if m=2 then
  for i:=1 to n-1 do
   for j:=i+1 to n do
    begin
    if i<>j then x:=0;go2(i,j);
    end;
if m=3 then
  for i:=1 to n-2 do
   for j:=i+1 to n-1 do
    for k:=j+1 to n do
      if (i<>j)and(i<>k)and(k<>j)then
      begin
      x:=0;go3(i,j,k);
      end;

assign(f,'train.out');rewrite(f);
writeln(f,max);close(f);


end.