该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

看起来你很喜欢网格图。

题目描述

• 给出一个 $n$ 行 $n$ 列的网格图，每个格子被染成黑色或白色。
• 初始情况下，若 $i + j$ 为奇数则 $(i,j)$ 被染成黑色，否则 $(i,j)$ 被染成白色。
• 现在有 $k$ 个格子的颜色被改变了，即如果是黑色则变为白色，如果是白色则变为黑色。
• 你需要找出一个子矩形，使得矩形中黑色格子和白色格子数量差的绝对值最大，并输出这个值。
• 你可以通过阅读样例解释更好地理解题意。

输入格式

从文件 diff.in 中读入。

• 第一行两个数 $n, k$，
• 接下来 $k$ 行，每行两个数 $x, y$，表示一个颜色被改变的格子，保证每个格子至多出现一次。

输出格式

输出到文件 diff.out 中。

• 一行一个整数表示答案。

样例输入输出

3 1  
1 1

3 4  
1 2  
2 1  
2 3  
3 2  

3 4  
1 1  
1 3  
3 1  
3 3

2  

9  

7

样例解释

【样例解释 1】 (1,1) 原本为白色，现在被染成了黑色，以 (1,1) 为左上角，(2,2) 为右下角的矩形中共有 3 黑 1 白，答案为 2。

【样例解释 2】 所有 9 个格子被染成了白色，答案为 9。

【样例解释 3】 除了 (2,2) 的 8 个格子被染成了黑色，答案为 7。

数据范围

• $1 \leq n\leq 10^9$
• $1\leq k\leq 50$

测试点分布

• 本题不设子任务捆绑
• 保证被改变颜色的点的位置在整个网格图中均匀随机
• 本题所有测试点等分
• 数据强度具有一定梯度
• 请留意本题不同寻常的时间限制

大样例下载

• 编号为 1 的大样例满足测试点 1~20 的限制
• 编号为 2 的大样例满足测试点 21~100 的限制