Minimum Phone Calls

In the Cute Village, there is a single long street that extends from east to west with \(m\) houses. The houses are numbered sequentially from \(1\) to \(m\). After a recent blizzard destroyed most of the telephone lines, the mayor funded the construction of a new telephone network. Mirko, curious about the adoption of this new network, installed special detectors at some points along the street.

A detector can detect any telephone call made between two houses if one house is to the east of the detector and the other house is to the west of the detector. At the end of the first month, Mirko removed all the detectors. Now he wonders: what is the minimum number of telephone calls that could possibly have been made during that month?

Each detector is placed at a position \(p\) (where \(1 \leq p \leq m-1\)), meaning that all houses numbered \(1,2,\dots,p\) lie to its east and all houses numbered \(p+1,p+2,\dots,m\) lie to its west. When a call is made between any two houses \(i\) and \(j\) (with \(i < j\)), every detector with a position \(p\) satisfying \(i \leq p < j\) will detect that call.

You are given the number of houses \(m\) and \(n\) detectors along with the reading \(r\) (i.e. the number of calls detected) for each detector. The detectors may be given in an arbitrary order. By choosing the houses that participate in each call optimally, determine the minimum number of calls that could have produced the detectors' readings.

A useful observation is that if you sort the detectors by their position, the minimum number of calls is given by:

[ \text{ans} = r_1 + \sum_{i=2}^{n} \max\Big(0, r_i - r_{i-1}\Big), ]

where \(r_i\) is the reading of the \(i\)th detector (after sorting by position) and \(r_1\) is the reading of the first detector.

inputFormat

The input begins with a line containing two integers \(m\) and \(n\) (with \(2 \leq m \leq 10^9\) and \(1 \leq n \leq 10^5\)), representing the number of houses and the number of detectors, respectively. Each of the next \(n\) lines contains two integers \(p\) and \(r\) where \(p\) (with \(1 \leq p \leq m-1\)) is the position of a detector and \(r\) (\(0 \leq r \leq 10^9\)) is the number of calls it detected. The detectors may be provided in an arbitrary order.

outputFormat

Output a single integer – the minimum number of telephone calls that could have been made during the month.

sample

5 3
1 2
3 3
4 1

3