题目描述

小 Z 有一棵线段树。

啥是线段树呢？你可以想象成，一开始，你有一个区间 $[1,n]$，然后，你可以取中点 $x=\frac{1+n}{2}$，把它划分成两个区间 $[1,x],[x+1,n]$。（之前那个区间 $[1,n]$ 也还在的哦）

然后，你可以继续划分下去，直到把每一个区间都划分成长度为 $1$ 为止，下图就是一棵线段树，维护了区间 $[1,10]$ 的信息。

假设线段树上，每个节点都存储了它表示的区间内所有元素的信息（比如区间的和）。

那么，当我想知道一个区间 $[l,r]$ 的信息的时候，我一定可以在线段树上找到一些区间，这些区间互相没有交集，且并起来刚好是区间 $[l,r]$。

比如，我在上图的线段树中，要查询 $[4,8]$ 的信息，那么我找到 $[4,5],[6,8]$ 两个区间，就可以表示区间 $[4,8]$ 的信息了。（把 $[6,8]$ 替代成 $[6,7],[8,8]$ 显然也是合法的策略，但是这样选择的区间更多了，不够优秀）。

我们称，对于一次查询 $[l,r]$，我们需要用到的区间个数为 $f_{l,r}$，比如上图中 $f_{4,8}=2,f_{1,6}=2$。

我们的问题是：给定线段树根节点所表示的区间范围是 $[1,n]$，以及有 $m$ 次查询，第 $i$ 次查询是 $[l_i,r_i]$，假设你可以在最初时候自由的选择区间分割的位置（每一层的区间划分都可以自由选择，而非只能自由选择划分 $[1,n]$），$\sum_{i=1}^{q} f_{l_i,r_i}$ 最小是多少？

输入格式

从 segment.in 文件读入数据。

第一行输入 $n,q$。

接下来 $q$ 行，每行两个数字 $l_i,r_i$。

输出格式

输出到 segment.out 文件。

一个数字表示答案。

样例

4 2
1 3
4 4

2

5 3
1 3
3 5
2 4

5

10 8
1 5
2 6
2 4
2 8
2 9
3 5
3 6
1 10

11

样例4

此样例满足 $n,q\leq 100$ 数据范围限制。

点击链接 ex_segment4.in 和 ex_segment4.out 下载大样例 4 的输入数据和输出数据。

样例5

此样例满足 $n,q\leq 500$ 数据范围限制。

点击链接 ex_segment5.in 和 ex_segment5.out 下载大样例 5 的输入数据和输出数据。

样例6

此样例满足 $n\le 500,q\leq 10^5$ 数据范围限制。

点击链接 ex_segment6.in 和 ex_segment6.out 下载大样例 6 的输入数据和输出数据。

说明/提示

样例 1 解释

对于我们来说，我们可以在第一层分割时候，把区间 $[1,4]$ 分割成 $[1,3],[4,4]$，这样两个查询都只需要一次操作。

样例 2 解释

我们在第一层把区间分割成 $[1,2],[3,5]$，然后把 $[3,5]$ 分割成 $[3,4],[5,5]$，$[3,4]$ 分割成 $[3,3],[4,4],[1,2]$ 分割成 $[1,1],[2,2]$。

这样，对于 $[1,3]$ 的查询，我们需要用到两个区间 $[1,2],[3,3]$。

数据范围

对于 $30\%$ 的数据：保证 $n\leq 10,q\leq 20$。

对于 $50\%$ 的数据：保证 $n,q\leq 100$。

对于 $70\%$ 的数据：保证 $n,q\leq 500$。

对于 $100\%$ 的数据：保证 $1\leq n \leq 500,1\leq q\leq 10^5,1\leq l_i\leq r_i\leq n$。