import sys def main(): N, M = map(int, sys.stdin.readline().split()) b = [[0 for _ in range(N)] for __ in range(N)] for _ in range(M): r, c = map(int, sys.stdin.readline().split()) r -= 1 c -= 1 b[r][c] = 1 # 情况一:先翻转行,再翻转列 # 计算各行的净收益,翻转收益为正的行 row_flips = [0] * N for r in range(N): k = sum(1 - b[r][c] for c in range(N)) if 2 * k - N > 0: row_flips[r] = 1 # 翻转行后的棋盘状态 b_flip_row = [row.copy() for row in b] for r in range(N): if row_flips[r]: for c in range(N): b_flip_row[r][c] ^= 1 # 计算各列的净收益,翻转收益为正的列 col_flips = [0] * N for c in range(N): k = sum(1 - b_flip_row[r][c] for r in range(N)) if 2 * k - N > 0: col_flips[c] = 1 # 翻转列后的棋盘状态 for c in range(N): if col_flips[c]: for r in range(N): b_flip_row[r][c] ^= 1 # 计算情况一的X操作次数 x_case1 = sum(1 - b_flip_row[r][c] for r in range(N) for c in range(N)) # 情况二:先翻转列,再翻转行 b_flip_col = [row.copy() for row in b] # 计算各列的净收益,翻转收益为正的列 col_flips2 = [0] * N for c in range(N): k = sum(1 - b[r][c] for r in range(N)) if 2 * k - N > 0: col_flips2[c] = 1 for c in range(N): if col_flips2[c]: for r in range(N): b_flip_col[r][c] ^= 1 # 计算各行的净收益,翻转收益为正的行 row_flips2 = [0] * N for r in range(N): k = sum(1 - b_flip_col[r][c] for c in range(N)) if 2 * k - N > 0: row_flips2[r] = 1 for r in range(N): if row_flips2[r]: for c in range(N): b_flip_col[r][c] ^= 1 x_case2 = sum(1 - b_flip_col[r][c] for r in range(N) for c in range(N)) # 情况三:不翻转行和列 x_case3 = sum(1 - b[r][c] for r in range(N) for c in range(N)) # 情况四:只翻转行和列中收益为正的,但不考虑顺序 # (这可能需要更复杂的计算,但为了节省时间,这里只比较情况一、二、三) # 选择最小的X操作次数 min_x = min(x_case1, x_case2, x_case3) print(min_x) if __name__ == "__main__": main()