008 - 募金街道

問題

トクイチさんは、イズア地方の民のために仏像を作ることを思い立ち、その資金を集めることにしました。トクイチさんは、旅をすると寄付金がよく集まると言われている街道、通称「募金街道」を旅する計画を立てています。

募金街道は街道沿いに町が並んだ一直線の街道で、その起点の町から終点の町まで順番に１から番号が付いています。トクイチさんはまず町１に入り、町２，町３、...と順番に進んでいきます。トクイチさんはすべての町で寄付金集めができますが、以下のルールに従わなければなりません。

• トクイチさんはそれぞれの町で集める寄付金の目標金額を決める。その町で目標金額まで集めたら、次の町に向かう。
• ある町で集める目標金額を０円にして、その町で寄付金を集めないことも可能だが、目標金額を負の値にすることはできない。
• 町１での目標金額は０円か１円のどちらかとする。
• 町１以外の町での目標金額は、その直前の町での目標金額から１円増やした金額、１円減らした金額、同じ金額のうちのどれかでなければならない。
• いくつかの町には関所があり、さらに以下のルールに従う。
• 関所がある町では、トクイチさんはその町で集める目標金額を関所に届け出なければならない。
• 関所ごとに定められた金額と届け出た金額が一致したときは、その町での募金活動が認められ、その先の町へも旅を続けられる。
• 関所ごとに定められた金額と届け出た金額が一致しなければ、その町での募金活動は認められず、旅もそこで終えなければならない。

たとえば、町３に関所があり、そこで定められた金額が２円とします。このとき、町１，２，３での目標金額をそれぞれ１円、２円、２円とすれば、町３での目標金額を関所で定められた金額と一致させることができます。

トクイチさんは関所ごとに定められた金額を突き止めました。その情報を元にして、どのように目標金額を決めれば、集める寄付金の総額を最大にできるか頭を悩ませています。

街道沿いの町の数と、関所がある町の番号と関所ごとに定められた金額が与えられたとき、トクイチさんが集められる寄付金の総額の最大値を計算するプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

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

１行目に街道沿いの町の数 $N$ ( 1 ≤ $N$ ≤ 1 , 000 , 000 , 000 )、関所の数 $M$ ( 1 ≤ $M$ ≤ min( $N$ , 100000 ))が与えられる。続く $M$ 行に関所がある町の番号 $a_i$ ( 1 ≤ $a_i$ ≤ $N$ )とその関所で定められた金額 $b_i$ ( 0 ≤ $b_i$ ≤ 1 , 000 , 000 , 000 )が与えられる。なお、 $i$ < $j$ のとき、 $a_i$ < $a_j$ である。

出力

トクイチさんが集められる最大の金額を１行に出力する。

入出力例

入力例1

5 1
3 2

出力例1

12

入力例2

7 1
5 6

出力例2

10

入力例3

5 2
2 2
4 0

出力例3

6