K. Silver Wolf and IPC (Novice)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The Interastral Peace Corporation (IPC) owns a permutation $$$a_1, a_2, \ldots, a_N$$$ of length $$$N$$$ ($$$2 \le N \le 10^3$$$).

Infamous hacker Silver Wolf has performed $$$Q$$$ ($$$1 \le Q \le 10^5$$$) operations to mess up the permutation:

  • "l r" — Rotate the interval $$$[l, r]$$$, ie. set $$$a_i = a_{i + 1}$$$ and $$$a_r = a_l$$$.

After these operations, the IPC will have to restore their permutation to its sorted form after reaching performing some swaps on it. However, they are not completely sure of the rotation that Silver Wolf will perform these operations in. Thus, they need you to find the sum of the minimum number of swaps the IPC will need to restore their permutation over all rotations of operations. Formally, let $$$o_0, o_1, \ldots, o_{Q - 1}$$$ be the operations. Silver Wolf may choose any non-negative integer $$$x$$$ and set $$$o_i = o_{(i + x)\%Q}$$$. Let $$$f(x)$$$ be the minimum number of swaps the IPC needs to restore their permutation for a given $$$x$$$ that Silver Wolf chooses. You need to find $$$\sum_{x=0}^{Q - 1} f(x)$$$.

Input

The first line contains two integers $$$N$$$ and $$$Q$$$ ($$$2 \le N \le 10^3$$$, $$$1 \le Q \le 10^5$$$).

The next $$$Q$$$ lines contain two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \lt r \le N$$$). The $$$i$$$-th line denotes that Silver Wolf will perform an operation rotating the interval $$$[l, r]$$$.

Output

Output a single integer, $$$\sum_{x=0}^{Q - 1} f(x)$$$.

Example
Input
5 2
1 4
2 5
Output
8
Note

For $$$x = 0$$$, the IPC's final permutation will be $$$[2, 4, 1, 5, 3]$$$. This can be sorted by swapping the indices $$$(1, 3)$$$, $$$(2, 3)$$$, $$$(3, 5)$$$, and $$$(4, 5)$$$ in that order.

For $$$x = 1$$$, the IPC's final permutation will be $$$[3, 4, 5, 1, 2]$$$. This can be sorted by swapping the indices $$$(1, 4)$$$, $$$(2, 5)$$$, $$$(3, 4)$$$, and $$$(4, 5)$$$ in that order.