说明

给定由糖果组成的𝑁堆块，标号为 1…𝑁，其中 𝑁 是一个奇数。接下来，有 𝐾 条指令，每条指令的形式为 A B，表示需要给第 𝐴…𝐵堆糖果堆都加入一个糖果。我们的任务是，在执行完所有指令后，找到糖果堆中糖果数量的中位数。

输入格式

第 $1$ 行：两个整数 $N$ 、 $K$ 。

第 $2 \dots K + 1$ 行：每行包括一条指令 A B ，其中 $1 \le A \le B \le N$ 。

输出格式

第 $1$ 行： 完成 所有指令后， $N$ 堆糖果数量的中位数。

样例

7 4
5 5
2 4
4 6
3 5

1

提示

有 $N = 7$ 堆糖果堆， $K = 4$ 条指令。第一条指令是给第 $5$ 堆加入一个糖果，第二条指令是给第 $2 \dots 4$ 堆加入一个糖果，以此类推。

完成所有指令后， $7$ 堆糖果的数量为 为 0,1,2,3,3,1,0 ，排序后为 0,0,1,1,2,3,3，中位数为 1。