Fundraising Street

Mr. Tokuichi has come up with the idea of making a Buddha statue for the people of the Isua region and has decided to raise funds for the project. He plans to travel along a road known as the "fundraising road," a road that is said to collect donations well when traveled.

A fund-raising highway is a straight line of towns lined up along the highway, numbered from 1 in order from the town at the beginning to the town at the end. The towns are numbered from one to the last, starting with town 1. Then he moves on to town 2, town 3, and so on. Mr. Tokuichi can collect donations in all towns, but he must follow the rules below.

• Mr. Tokuichi sets a target amount of donations to be collected in each town. Once he has raised the amount of money he set for that town, he will move on to the next town.
• It is possible to set the target amount to be collected in a certain town to zero and not collect donations in that town, but it is not possible to set the target amount to a negative value.
• The target amount in town 1 is either 0 yen or 1 yen.
• The target amount in any town other than town 1 must be either an increase of 1 yen, a decrease of 1 yen, or the same amount as the target amount in the immediately preceding town.
• Some towns have gates and are further subject to the following rules.
  • In towns with a customs office, Tokuichi must notify the customs office of the target amount of money to be collected in that town.
  • When the amount of money reported matches the amount of money set by each customs office, the fund-raising activity is allowed to continue in that town, and the journey to the next town is allowed to continue.
  • If the amount of money reported does not match the amount set by each customs office, the fundraising activities in that town will not be allowed and the trip must end there.

For example, let's say there is a customs office in town 3 and the amount of money set there is 2 yen. In this case, if the target amount in towns 1, 2, and 3 is 1 yen, 2 yen, and 2 yen, respectively, the target amount in town 3 will match the amount set at the customs office.

Mr. Tokuichi has found out the amount of money set for each barrier. Based on this information, he is trying to figure out how to set a target amount to maximize the total amount of donations collected.

Given the number of towns along the street, the number of the town with the customs office, and the amount of money specified for each customs office, create a program that calculates the maximum total amount of donations that Tokuichi can collect.

Input

Input is given in the following format.

$N$ $M$
$a_1$ $b_1$
$a_2$ $b_2$
 :
$a_M$ $b_M$ 

In the first line, we are given the number of towns along the road, $N$ ($1 \leq N \leq 1,000,000,000$), and the number of customs offices, $M$ ($1 \leq M \leq $min($N, 100000$)). The following $M$ line gives the number of the town where the customs office is located, $a_i$ ($1 \leq a_i \leq N$), and the amount of money specified for that customs office, $b_i$ ($0 \leq b_i \leq 1,000,000,000$). Note that when $i < j$, $a_i < a_j$.

Output

Output the maximum amount of money that Tokuichi can collect on a single line.

Sample Input and Output

Sample Input １

5 1
3 2

Sample Output １

12

Sample Input ２

7 1
5 6

Sample Output ２

10

Sample Input ３

5 2
2 2
4 0

Sample Output ３

6

---