CF406E.Hamming Triples

小 Chris 正在做噩梦。即使在梦里，他脑海里想的全是数学。

Chris 梦见有 $m$ 个长度为 $n$ 的二进制字符串，这些字符串的编号从 1 到 $m$。最可怕的是，每个字符串的比特都是按升序或降序排列。例如，Chris 可能梦到如下 4 个长度为 5 的字符串：

汉明距离 $H(a,b)$ 表示长度为 $n$ 的两个字符串 $a$ 和 $b$ 在每个对应位置上不同的个数。

Chris 认为，任意三个下标各不相同的字符串组成了一个三元组。在 Chris 的妄想中，只有当他数出了所有满足 $H(a,b)+H(b,c)+H(c,a)$ 在所有可能的字符串三元组中最大的那些三元组数量时，他才能醒来。

请帮助 Chris 从噩梦中醒来！

输入的第一行包含两个用空格分隔的整数 $n$ 和 $m$（$1\leq n\leq 10^{9}$；$3\leq m\leq 10^5$），表示字符串的长度和数量。接下来的 $m$ 行每行包含两个用空格分隔的整数 $s_i$ 和 $f_i$（$0\leq s_i\leq 1$；$1\leq f_i\leq n$），描述第 $i$ 个字符串：即第 $i$ 个字符串的前 $f_i$ 位全为 $s_i$，剩下的 $n-f_i$ 位全为 $1-s_i$。Chris 梦里的字符串可以有多个是完全相同的。

输出一个整数，表示在给定的字符串中，三元组 $(a, b, c)$ 之间所有三对两两之间汉明距离之和最大的三元组数量。

由 ChatGPT 5 翻译