Light
 
提交文件：count.pas count.exe
文件输入：count.in
文件输出：count.out
一天，Mpq的物理老师找到Mpq说：“你学过光现象的一些知识了，我知道你是学信息学的，现在我结合物理来问你一个信息学的问题(我晕，物理老师也懂信息学)。” Mpq很爽快的答应了，他认为物理老师的问题不会很难的。
 
王老师接着说：“你知道光在同一均匀物质中是沿直线传播的。我现在有一些箱子，放在一堵长N米的墙前面，然后我向它们的正面射光线，那么在墙上就会有箱子的影子，问最后所有箱子影子的总长度是多少。”Mpq听了问题之后就觉得这是一个非常简单的题，就用最一般的方法就可以解决了，所以他暗暗的笑。王老师看到他得意的样子，笑着说：“你先别得意，我还没说出墙的范围和箱子的长度范围呢，下面我说说他们的范围，你可别吓个半死啊！。”
 
Input
   数据的第一行有两个正数N(n<=10000000)表示抢的长度。M(m<=1000000)，表示有多少个箱子。然后下面有M行，每行两个数x,y(x<y<=n);分别表示箱子的起始位置和终止位置。比如一个箱子的起始位置是1,终止位置是5,那么这个箱子的长度是5-1=4.
 
我晕，原来可以达到1000万啊，靠，最多还可以有100万个箱子，妈啊，这个题应该怎么做？为了Mpq不在王老师面前丢脸，他请来你这位超级大牛来帮他解决问题。
 
Output
   输出一个整数，表示箱子影子的总长度。
 
样例输入：
6 4
1 2
3 5
4 6
5 6
 
样例输出：
4
 
对于样例，可以参照下图：
 
1     2      3       4      5      6
1
1
1
0
1  
 
 
 
 
数据说明：
  对于30%的数据，n<=20000,m<=1000;
  对于60%的数据，n<=4000000;m<=500000;
  对于100%的数据，n<=10000000,m<=1000000;

type integer=longint;
type link=^data;
     data=record
       l,r:integer;
       c:integer;
       lc,rc:link;
     end;
var
  head,first:link;
  l,r,n,i,len:integer;

procedure insert(var first:link;l,r:integer);
var
  m:integer;
begin
  if first^.c=0 then
  begin
    m:=(first^.l+first^.r) div 2;
    if (first^.l=l)and(first^.r=r) then
      first^.c:=1 else
    if r<=m then insert(first^.lc,l,r) else
    if l>=m then insert(first^.rc,l,r) else
    begin
      insert(first^.lc,l,m);
      insert(first^.rc,m,r);
    end;
  end;
end;

procedure dfs(var first:link;l,r:integer);
var
  m:integer;
begin
  if r-l=1 then
  begin
    first^.l:=l;
    first^.r:=r;
    first^.c:=0;
    exit;
  end else
  begin
    m:=(l+r) div 2;
    new(first^.lc);
    new(first^.rc);
    dfs(first^.lc,l,m);
    dfs(first^.rc,m,r);
  end;
  first^.l:=l;
  first^.r:=r;
  first^.c:=0;
end;

function count(firsts:link):integer;
begin
  if firsts^.c=1 then
    count:=firsts^.r-firsts^.l else
  if firsts^.r-firsts^.l=1 then count:=0 else
  begin
    count:=count(firsts^.lc);
    count:=count+count(firsts^.rc);
  end;
end;

begin
  new(head);
  first:=head;
  readln(len);
  dfs(first,1,len);
  readln(n);
  for i:=1 to n do
  begin
    first:=head;
    readln(l,r);
    insert(first,l,r);
  end;
  first:=head;
  writeln(count(first));
end.