G - ピラミッド - 球編 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

伊織ちゃんのマイブームはピラミッドである。

伊織ちゃんは半径が 1 である球状の石 L \times (L+1) \times (L+2) / 6 個を 1 辺が L 個となる正四面体状に並べて、ピラミッドのようなものを作ろうとしている。安定して机に置くことができるように、L \times (L+1) / 2 個の円状の穴があいた木の板の上に並べようとしている。しかし、穴をあけるときに失敗をしてしまい、いくつかの穴には石を置けなくなってしまった。正四面体状に並べるときと同じように石を並べていくと、伊織ちゃんはいくつの石を置くことができるだろうか。ただし「正四面体状に並べるときと同じように石を並べていく」とは、以下のような並べ方のことである。

  • 正四面体状に石を並べるときに、下から i (1 ≦ i ≦ L) 段目、奥から j (1 ≦ j ≦ L-i+1) 列目、左から k (1 ≦ k ≦ j) 個目の石を置くはずだった位置を位置 (i,j,k) と呼ぶことにする。ただし、下から 1 段目の奥から x (1 ≦ x ≦ L) 列目に x 個の石が並ぶような向きで置くことを考えているものとする。
  • まず、下から 1 段目の位置のうち、穴をあけるのに成功していて石を置けるような場所に全て石を置く。
  • 下から 2 段目から L 段目の位置 (i,j,k) のうち、位置 (i-1,j,k) にも位置 (i-1,j+1,k) にも位置 (i-1,j+1,k+1) にも石があるような位置に石を置く、という操作を石を置ける位置がなくなるまで繰り返す。

入力

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

L N
A_1 B_1
A_2 B_2
:
A_N B_N
  • 1 行目には、2 つの整数 L (2 ≦ L ≦ 10^5), N (0 ≦ N ≦ Min(10^5, L \times (L+1) / 2)) が空白区切りで与えられる。これは、1 辺が L 個となる正四面体状に石を並べる予定であったことと、穴をあけるのに失敗した位置が N 個あるということを表す。
  • 2 行目からの N 行には、穴をあけるのに失敗した位置の情報が与えられる。このうち i (1 ≦ i ≦ N) 行目には、2 つの整数 A_i (1 ≦ A_i ≦ L), B_i (1 ≦ B_i ≦ A_i) が与えられる。これは、奥から A_i 列目、左から B_i 個目の穴をあけるのに失敗したということを表す。ただし、同じ位置の情報が 2 回以上与えられないことが保証される。

部分点

この問題には部分点が設定されている。

  • N ≦ 20 を満たすデータセット 1 に正解した場合は、58 点が与えられる。
  • 全てのテストケースに正解した場合は、満点が与えられる。

出力

伊織ちゃんが置く石の個数を 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

3 1
2 1

出力例1

6

位置 (1,1,1)、位置 (1,2,2)、位置 (1,3,1)、位置 (1,3,2)、位置 (1,3,3)、位置 (2,2,2) の 6 箇所に石を置くことができる。

入力例2

100000 0

出力例2

166671666700000

このように、穴をあけるのに実は失敗していなかったということもありうるので注意すること。

入力例3

6 4
3 2
6 6
5 2
3 3

出力例3

25