Minimizing the Cut Grass Area

On a square field of size \(T\times T\) (with grid points from \((0,0)\) to \((T,T)\)) the cows Ella and Bella start at \((0,0)\) and run to \((T,T)\) taking steps of length 1 per second. They can only move either right or up along the grid. They hold opposite ends of a very elastic, sharp wire so that every region swept by the wire is cut.

Bessie is worried that too much grass might be cut by their mischief. To limit their choice of paths, she scatters \(N\) different kinds of flowers at fixed grid points on the field. She then selects a subset \(S\) of these flowers and forces both cows to visit every flower in \(S\) on their way. Knowing they will choose their individual paths to maximize the cut area, Bessie’s goal is to constrain them as much as possible.

In particular, Bessie is allowed to choose \(S\) arbitrarily from the given flowers, but she wants \(S\) to be as large as possible (i.e. the cows must visit a longest possible increasing chain of flower positions) and, among all such choices, she wants the maximum cut area (calculated under the assumption that the cows choose their routes to maximize the area) to be minimized.

Note that since the cows can only move right or up, a sequence of points \(p_1, p_2, \dots, p_k\) (with coordinates \((x_i,y_i)\)) is traversable if \(x_1 < x_2 < \cdots < x_k\) and \(y_1 < y_2 < \cdots < y_k\). Bessie will force the cows to go through a chain \(p_1, p_2, \dots, p_r\) of flowers (with \(r\) as large as possible), so that the paths from \((0,0)\) to \(p_1\), from \(p_1\) to \(p_2\), \(\dots\), from \(p_r\) to \((T,T)\) are each forced to include a flower. In any segment from a point \((a,b)\) to a point \((c,d)\) (with \(a<c\) and \(b<d\)), the cows may choose one path to go right then up and the other to go up then right; the area cut in that segment is \((c-a)\times(d-b)\).

The total cut area is the sum of areas over segments. Your task is to compute the minimum possible total cut area (over all choices of a longest increasing chain \(S\)) when the cows will choose their paths in each segment to maximize this area.

Mathematical formulation:

Let \(S = \{(x_1,y_1), (x_2,y_2), \dots, (x_r,y_r)\}\) be an increasing chain, i.e. \(0<x_1< x_2 < \cdots < x_r<T\) and \(0<y_1< y_2< \cdots < y_r<T\). Define \(p_0=(0,0)\) and \(p_{r+1}=(T,T)\). The cut area if the cows are forced to go through \(S\) is:

[ A = \sum_{i=0}^{r} \Bigl((x_{i+1}-x_i)\cdot(y_{i+1}-y_i)\Bigr). ]

Bessie wants to choose \(S\) so that \(r\) is maximized (i.e. as many flowers are forced) and, among all chains of maximum length, \(A\) is minimized.

inputFormat

The first line contains two integers \(T\) and \(N\) (\(1 \le T \le 10^9\), \(1 \le N \le 2\times10^5\)).

Each of the next \(N\) lines contains two integers \(x\) and \(y\) — the coordinates of a flower. All flower coordinates satisfy \(0 \le x,y \le T\). Note that the cows’ start \((0,0)\) and end \((T,T)\) are fixed and not counted as flowers.

outputFormat

Output a single integer — the minimum total area (in square units) that will be cut by the cows if they choose their paths to maximize the area in every segment while being forced to pass through a longest increasing chain of flowers.

sample

10 2
3 4
7 8

34