Lights of Apartment

Problem

エーちゃんとリカちゃんとハルトくんはマンションに遊びに来た。
3人は全ての部屋の電気を管理できる部屋に忍び込みいたずらをすることにした。

このマンションはn個の立方体が1列に並んでいる形をしている。
各立方体は西から順に1辺の長さが1ずつ増えていて(1,2,3,...,n)、i番目の立方体はi階あり、各階に縦i×横i個の部屋がある。
2番目以降の立方体の西側は1つ西の立方体の東側と接していて、全ての立方体の南側は真っ直ぐな道路に面している。

初め全ての部屋に電気がついている。
3人はそれぞれ次の行動をした。

• エーちゃんは西からk番目の全ての部屋の電気を消した。
• リカちゃんは南からk番目の全ての部屋の電気を消した。
• ハルトくんはk階の全ての部屋の電気を消した。

このようないたずらが m 回行われた後に電気がついている部屋の数を求めよ。

Input

n m
q1 k1
...
qm km

入力は全て整数で与えられる。
1行目に立方体の数n、行動の数mが与えられる。
2行目以降m行に行動した人の番号qとkが与えられる。

q_iが0の場合エーちゃん、 1の場合リカちゃん、2の場合ハルトくんが行動したことを表す。

3人は部屋がない場所の電気を消そうとすることもある。

Constraints

• 1 ≤ n,m ≤ 50000
• 0 ≤ q_i ≤ 2
• 1 ≤ k_i ≤ 2×10⁹
• 同じ行動は一度しか与えられない

Output

電気がついている部屋の数を1行に出力せよ。

Sample Input 1

3 1
0 4

Sample Output 1

27

Sample Input 2

3 2
2 2
2 3

Sample Output 2

14

---