007 - 税の徴収

問題

イヅア村には$1$から$N$までの番号が付いた$N$軒の家がある。この村では、$M$人の徴税官が税を徴収する。徴税官は家を訪れて税金を徴収する。$1$軒の家で徴収する金額は、徴税官ごとに決まっている。

はじめに、徴税官はそれぞれ異なる家に派遣され、そこで税金を徴収する。 次に、徴税官がいる家のうち番号が一番小さい家にいる徴税官が、それよりも大きい番号の家のうち、まだ徴税が済んでいない最も番号が小さい家に移動し、そこで税金を徴収する。これを繰り返し、どの徴税官も税金を徴収できなくなったら徴収を終える。

家の軒数と徴税官の人数、各徴税官が徴収する金額と最初に派遣される家の番号が与えられたとき、イヅア村から徴収できる税金の総額を求めるプログラムを作成せよ。

入力

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

$N$ $M$
$t_1$ $h_1$
$t_2$ $h_2$
:
$t_M$ $h_M$

１行目に家の軒数$N$($1 \leq N \leq 100,000$)と徴税官の人数$M$($1 \leq M \leq N$)が与えられる。続く$M$行に$i$番目の徴税官が徴収する税金の金額$t_i$($1 \leq t_i \leq 10,000$)と最初に派遣される家の番号$h_i$($1 \leq h_i \leq N$)が与えられる。ただし、異なる徴税官が同じ家に最初に派遣されることはない（$i$≠$j$ならば$h_i$≠$h_j$)。

出力

イヅア村から徴収できる税金の総額を1行に出力する。

入出力例

入力例1

6 2
2 1
3 3

出力例1

14

入力例2

7 3
3 4
2 3
5 7

出力例2

15