← 返回题目列表

Codeforces · 406/E

E. 汉明三元组

中文机器翻译题面 查看原题

小克里斯做了一场噩梦。即使在梦中,他脑子里也只有数学。

Chris 梦想 m 个长度为 n 的二进制字符串,用从 1 到 m 的数字进行索引。最可怕的是,每个字符串的位都按升序或降序排列。例如,Chris 可能会梦见以下 4 个长度为 5 的字符串:

长度为n的两个字符串a和b之间的汉明距离H(a,b)是对应符号不同的位置的数量。

Сhris 认为每三个具有不同索引的字符串构成一个三元组。克里斯的错觉是,只有当他计算出这样的字符串三元组 a、b、c 的数量,并且 H(a, b) + H(b, c) + H(c, a) 之和在由梦到的字符串构造的所有字符串三元组中最大时,他才会醒来。

帮助克里斯从这场噩梦中醒来!

输入

输入的第一行包含两个空格分隔的整数 n 和 m (1 ≤ n ≤ 109; 3 ≤ m ≤ 105)、字符串的长度和数量。接下来的 m 行包含字符串的描述。第 i 行包含两个空格分隔的整数 si 和 fi (0 ≤ si ≤ 1; 1 ≤ fi ≤ n),索引为 i 的字符串的描述;这意味着第 i 个字符串的前 fi 位等于 si,其余 n - fi 位等于 1 - si。克里斯的梦中可以有多个相等的弦。

输出

输出一个整数,在给定的三元组字符串之间的汉明距离之和最大的情况下,此类字符串三元组的数量。

示例

输入 #1

5 4
0 3
0 5
1 4
1 5

输出 #1

3

输入 #2

10 4
1 5
0 5
0 5
1 5

输出 #2

4