I. Sequence
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Nakisa likes sequence. She is interested in sequence $$$P$$$ which meets the following conditions:

  • Lenth of $$$P$$$ is $$$N$$$ and the index is from $$$1$$$ to $$$N$$$.
  • $$$\forall P_i \in [1,N]$$$ .
  • There exists some restrictions $$$(index,value)$$$ , indicating that $$$P_{index}$$$ cannot be $$$value$$$ ($$$1 \le index,value \le N$$$) .

Nakisa does not care sequence itself, he only wants to know how many ordered tuples $$$(A,B,L,R)$$$ satisfies $$$\forall i \in[A,B]$$$ , $$$P_i$$$ can be any number in $$$[L,R]$$$ , ($$$1 \le A,B,L,R \le N$$$ , $$$A \le B$$$ and $$$L \le R$$$).

For example, $$$N=2$$$, one restriction is $$$P_2$$$ cannot be $$$1$$$. There are 5 vaild tuples, and they are as the follows:

  • $$$(1,1,1,1)$$$
  • $$$(1,1,1,2)$$$
  • $$$(1,1,2,2)$$$
  • $$$(1,2,2,2)$$$
  • $$$(2,2,2,2)$$$

An invaild tuple is $$$(2,2,1,1)$$$ because $$$P_2$$$ cannot be $$$1$$$.

Input

First line contains two numbers $$$N$$$ ($$$1 \le N \le 5000$$$) and $$$M$$$ ($$$0 \le M \le 1000000$$$). Indicatiing the lenth of the sequence and the number of restrictions.

In the following $$$M$$$ lines, each line contains two number $$$a$$$ and $$$b$$$ ($$$1 \le a,b \le N$$$). Indicating a restriction that $$$P_a$$$ cannot be $$$b$$$.

Output

One number indicating the answer.

Examples
Input
2 1
2 1
Output
5
Input
3 5
1 1
2 1
3 1
3 2
3 3
Output
9
Note
  • Attention that there may be some same restrictions.
  • You are supposed to use faster IO method like scanf in C/C++ due to the huge amount of input.