program train;
const
  maxn=100;
var
  f1:array[0..maxn]of longint;
  f2:array[-1..maxn,-1..maxn]of longint;
  f3:array[-2..maxn,-2..maxn,-2..maxn]of longint;
  t:array[-2..maxn,1..2]of longint;
  i,j,k,m,n:longint;
procedure find1(p1:longint);
  var
    p2:longint;
  begin
    if f1[p1]<>0 then{f1[p1]表示当前站内正在停p1号车时，最多还能有多少车进站}
      exit;
    f1[p1]:=1;
    for p2:=p1+1 to n do{枚举下一辆车}
      if t[p2,1]>=t[p1,2] then
        begin
          find1(p2);
          if f1[p2]+1>f1[p1] then
            f1[p1]:=f1[p2]+1;
        end;
  end;
procedure find2(p1,p2:longint);
  var
    p3:longint;
  begin
    if f2[p1,p2]<>0 then{f2[p1,p2]表示当前站内正在停p1,p2号车时，最多还能有多少车进站}
      exit;
    f2[p1,p2]:=1;
    for p3:=p2+1 to n do{枚举下一辆车}
      if (t[p3,2]>=t[p2,2])and(t[p3,1]>=t[p1,2]) then
        begin
          find2(p2,p3);
          if f2[p2,p3]+1>f2[p1,p2] then
            f2[p1,p2]:=f2[p2,p3]+1;
        end;
  end;
procedure find3(p1,p2,p3:longint);
  var
    p4:longint;
  begin
    if f3[p1,p2,p3]<>0 then{f3[p1,p2,p3]表示当前站内正在停p1,p2,p3号车时，最多还能有多少车进站}
      exit;
    f3[p1,p2,p3]:=1;
    for p4:=p3+1 to n do{枚举下一辆车}
      if (t[p4,2]>=t[p3,2])and(t[p4,1]>=t[p1,2]) then
        begin
          find3(p2,p3,p4);
          if f3[p2,p3,p4]+1>f3[p1,p2,p3] then
            f3[p1,p2,p3]:=f3[p2,p3,p4]+1;
        end;
  end;
begin
  assign(input,'train.in');reset(input);
  readln(n,m);
  for i:=1 to n do
    readln(t[i,1],t[i,2]);
  close(input);

  for i:=1 to n do{按进站时间排序，其次按出站时间排序，这样动规可以得到最大值}
    for j:=i+1 to n do
      if (t[i,1]>t[j,1])or(t[i,1]=t[j,1])and(t[i,2]>t[j,2]) then
        begin
          t[0]:=t[i];t[i]:=t[j];t[j]:=t[0];
        end;

  for i:=-2 to 0 do{边界条件}
    for j:=1 to 2 do
      t[i,j]:=t[1,1]-1;

  assign(output,'train.out');rewrite(output);
  case m of{对m分情况讨论，因为状态可能不多，所以采用记忆化搜索比较合适}
    1:begin
        find1(0);
        writeln(f1[0]-1);
      end;
    2:begin
        find2(-1,0);
        writeln(f2[-1,0]-1);
      end;
    3:begin
        find3(-2,-1,0);
        writeln(f3[-2,-1,0]-1);
      end;
  end;
  close(output);
end.