题目描述

打败兰斯洛特后，你和konnyaku终于来到了大魔王——鲁路修·Vi·不列颠尼亚面前。

要想战胜他可不容易，在鲁路修面前有一条长度为 $l$ 的路，可以看做从 $1$ 到 $l$ 的一条轴，鲁路修会下 $n$ 道命令，使得从 $a$ 到 $b$ 这个区间上每一个整数点上布置兵力，具体表现为如果这个区间的整数点原本没有兵力，就布置 $1$ 个兵；如果有兵力，则士兵的数量翻倍，而要想到他的面前，需要把整条路上所有的士兵打败。

作为魔法师，你需要计算出，在鲁路修下达完所有命令之后，需要打败的士兵的总数量。

输入格式

第一行 $2$ 个整数$l$、$n$，分别表示路的长度和鲁路修下达的命令数量。 接下来 $n$ 行每行两个整数 $a$ 和 $b$ ，表示鲁路修将要在 $a$ 到 $b$ 之间的每一个点布置兵力。

输出格式

一行一个整数，表示需要打败的士兵总数量。

样例输入

10 3
1 6
4 8
2 5

样例输出

17

样例分析

第一道命令，在1到6上各布置了一个兵；

第二道命令，使得4、5、6上兵力翻倍，各有两个兵，7、8上布置了一个兵；

第三道命令，使得2到5上的兵力翻倍，2、3上有两个兵，4、5上有四个兵。

共计1+2+2+4+4+2+1+1+0+0=17个士兵。

数据范围

$100\%$ 的数据：$1 \leq l \leq 1000$、 $0 \leq n \leq 50$;

对于每组a、b,保证 $1 \leq a \leq l$， $1 \leq b \leq l$。