B. Чипүүд

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Жералд дараах тоглоомыг тоглоно. Түүнд $m$ ширхэг аюултай нүд агуулсан $n × n$ хэмжээтэй шатрын хөлөг байгаа. Тоглолтын өмнө тэр булангуудаас бусад зарим ирмэгүүд дээр чип байршуулна. Түүний дараагаар $n - 1$ минут бүр Жералд бүх чипийг хөрш нүд рүү хөдөлгөнө. Хөрш нүд рүү хөдөлгөнө гэдэг нь чипний байрлаж байгаа ирмэгийн эсрэг зүгт орших хөрш нүдэнд авачихыг хэлнэ. Жералд дараах 3 тохиолдолд ялагдана:

  • Аль нэг чип нь аюултай нүд нь дээр очсон тохиолдолд.
  • Дор хаяж ганц удаа 2 чип нэг нүд нь дээр байрлах үед.
  • Дор хаяж ганц удаа 2 чип байрлалаа солисон үед (энэ нь хөлөг тэгш урттай тохиолдолд хөлгийн голд тохиолдоно).

Энэ тохиолдлуудад Жералд ялагдаж $0$ оноо авна. Хэрэв ийм зүйл тохиолдоогүй тохиолдолд тэр хөлөг дээр байршуулсан чипний тоотой тэнцэх хэмжээний оноо авна. Жералдад хамгийн их оноо авахад нь тусла.

Оролт

Эхний мөрөнд хөлгийн хэмжээг илтгэх $n$ болон аюултай нүдний тоо болох $m$ ($2 ≤ n ≤ 1000, 0 ≤ m ≤ 10^5$)тоонууд өгөгдөнө. Дараагийн $m$ мөрөнд $i$ дахь аюултай нүдний байрлалыг заах $x_i, y_i$ ($1 ≤ x_i, y_i ≤ n$) тоонууд өгөгдөнө. Бүх аюултай нүднүүд ялгаатай байна.

Мөрүүдийг дээрээс нь доош 1-ээс $n$ хүртэл дуугаарласан. Багнуудыг зүүнээс баруун тийш 1-ээс $n$ хүртэл дугаарласан.

Гаралт

Жералдын авч чадах хамгийн их оноог хэвлэ.

Орчуулсан: Энхсанаа

Жишээ тэстүүд

Оролт
3 1
2 2
Гаралт
0
Оролт
3 0
Гаралт
1
Оролт
4 3
3 1
3 2
3 3
Гаралт
1

Тэмдэглэл

In the first test the answer equals zero as we can't put chips into the corner cells.

In the second sample we can place one chip into either cell (1, 2), or cell (3, 2), or cell (2, 1), or cell (2, 3). We cannot place two chips.

In the third sample we can only place one chip into either cell (2, 1), or cell (2, 4).

Сэтгэгдлүүдийг ачааллаж байна...