Codeforces Round 194 (Div. 1) |
---|
Закончено |
Геральд играет в следующую игру. У него есть клетчатое поле размера n × n клеток, причем m различных его клеток запрещены. Перед началом игры он должен поставить несколько фишек на некоторые крайние (но не угловые) клетки доски. Затем в течение n - 1 минуты раз в минуту Геральд двигает каждую фишку в соседнюю клетку, продвигая ее от ее исходного края к противоположному краю. Геральд двигает все фишки одновременно. Геральд проигрывает в этой игре в каждом из трех случаев:
В таком случае он проигрывает и зарабатывает 0 очков. Если ничего такого не случилось, то он выигрывает и зарабатывает столько очков, сколько фишек ему удалось поставить на доску. Помогите Геральду заработать как можно больше очков.
В первой строке записаны через пробел два целых числа n и m (2 ≤ n ≤ 1000, 0 ≤ m ≤ 105) — размер поля и количество запрещенных клеток. В следующих m строках записаны по два целых числа в строке, разделенных пробелом. А именно, в i-той из этих строк записаны числа xi и yi (1 ≤ xi, yi ≤ n) — координаты i-той запрещенной клетки. Ни одна из запрещенных клеток не упомянута больше одного раза.
Считайте, что строки поля пронумерованы сверху вниз от 1 до n, а столбцы — слева направо от 1 до n.
Выведите единственное целое число — максимальное количество очков, которое может заработать Геральд в этой игре.
3 1
2 2
0
3 0
1
4 3
3 1
3 2
3 3
1
В первом тесте ответ равен нулю, так как нельзя ставить фишки в угловые клетки.
Во втором тесте, можно поставить одну фишку в клетку (1, 2), либо в клетку (3, 2), либо в клетку (2, 1), либо в клетку (2, 3). Две фишки поставить нельзя никак.
В третьем примере, можно поставить только одну фишку в клетку (2, 1), либо в клетку (2, 4).
Название |
---|