Sengoku(戦国時代) - joi2010-day1

時間制限: 0.75秒

メモリ制限: 64MB

時は戦国時代のまっただ中. JOI国を率いるJOI武将は, 来たるべき戦いに備え, 自らの領地に見張りを配備することになった.

JOI国の領地は, 東西幅、南北幅がLの正方形の形をしている. 領地は1×1の正方形の区画に分かれており, 各区画は0 ≤ x < L, 0 ≤ y < Lを満たす整数x,yによって(x,y)と表現される. 区間(0,0)は北西隅の区画であり, 区画(x,y)は, 区画(0,0)から東にx, 南にy進んだ地点に位置する区画である.

それぞれの見張りは領地内のある区画にとどまり, 次のような範囲を見張る. (x,y)の位置にいる見張りは, 条件 |x – i| = |y – j| をみたす領地内の区画(i,j)全体を見張る(この範囲は, 他の見張りの位置によって変化することはない). なお, 同一の区画に2人以上の見張りがいるということはない.

課題(TASK)

JOI武将が配備したN人の見張りの場所が与えられると, 少なくとも1人以上の見張りに見張られている領地内の区画の個数を求めるプログラムを作成せよ.

制限(CONSTRAINTS)

1 ≤ L ≤ 100,000,000	領地の1辺の長さ
1 ≤ N ≤ 100,000	見張りの数

入力(INPUT)

標準入力から以下の入力を読み込め.

1行目には整数LとNが空白を区切りとして書かれている.
続くN行は, 1行につき1人の見張りについて記述している. これらの行のうちのi行目はi番目の見張りについて記述しており, 整数x[i]とy[i] (0 ≤ x[i] < L, 0 ≤ yi < L) が空白を区切りとして書かれている.

出力(OUTPUT)

標準出力に以下のデータを出力せよ.

1行目には, 1人以上の見張りによって見張られている区画の個数を表す, 1つの整数が含まれていなければならない.

採点基準(GRADING)

15点分のテストグループにおいて, L,N は1,000を超えない. また, 40点分のテストグループにおいて, Nは1,000を超えない.

入出力例(EXAMPLE)

入力例(Sample Input)	出力例(Sample Output)
`5 4 4 1 1 1 1 0 3 3`	`18`

このときのJOI 国を図示すると, 下のようになる. 見張られている区画の個数は18である(黒丸は見張りを表す. また, 見張られている区画は灰色で示されている).