This is an extension of othscc4p5. In this version, the constraints and input format are different.

Aether is travelling across Teyvat, which can be represented by a ~N~ by ~N~ grid, where each cell ~A_{i,j}~ is either empty . or contains a teleporter x. Due to terrain and weather reasons, he can only move down and to the right. Formally, if he is at the cell ~(r, c)~, he can go to ~(r + 1, c)~ if ~r \neq N~, and he can go to ~(r, c + 1)~ if ~c \neq N~.

Whenever he is at a cell containing a teleporter, he can choose to teleport to any other cell containing a teleporter. Each teleporter can be used an unlimited number of times.

There will be ~K~ teleporters in total, the ~i^{th}~ of which is located at ~(r_i, c_i)~. No ~2~ teleporters will be at the same cell.

Since Aether likes exploring new areas, he would like to know, what is the maximum number of unique cells ~(r, c)~ that he can visit if he starts at the top-leftmost cell ~(1, 1)~?

Constraints

~1 \le N \le 10^9~

~1 \le K \le \min(N^2, 4 \times 10^5)~

~1 \le r_i, c_i \le N~

No ~2~ teleporters will be at the same cell.

Subtask 1 [85%]

~1 \le N \le 10^6~

Subtask 2 [15%]

No additional constraints.

Input Specification

The first line of input contains ~2~ space-separated integers, ~N~ and ~K~, representing the dimensions of the grid and the number of teleporters respectively.

The next ~K~ lines of input each contain ~2~ space-separated integers, ~r_i~ and ~c_i~, representing the location of the ~i^{th}~ teleporter.

Output Specification

Output ~1~ integer, the maximum number of unique cells that Aether can visit.

Sample Input 1

3 2
2 3
3 2

Sample Output 1

6

Explanation for Sample 1

The grid looks like this:

...
..x
.x.

The following path visits ~6~ unique cells:

• Start at ~(1, 1)~
• Go to ~(1, 2)~
• Go to ~(1, 3)~
• Go to ~(2, 3)~
• Teleport to ~(3, 2)~
• Go to ~(3, 3)~

It can be proven that this is the maximum number of unique cells Aether can visit.

Sample Input 2

5 5
1 1
2 2
3 4
5 2
5 5

Sample Output 2

25

Explanation for Sample 2

The grid looks like this:

x....
.x...
...x.
.....
.x..x