题目描述

qmqmqm 希望给 sublinekelzrip 出一道可做题。于是他想到了这么一道题目：给一个长度为 $n$ 的非负整数序列 $a_i$，你需要计算其异或前缀和 $b_i$，满足条件 $b_1=a_1,b_i=b_{i-1}\operatorname{xor}a_i(i \geq 2)$。

但是由于数据生成器出现了问题，他生成的序列 $a$ 的长度特别长，并且由于内存空间不足，一部分 $a_i$ 已经丢失了，只剩余 $m$ 个位置的元素已知。现在 qmqmqm 找到你，希望你根据剩余的 $a_i$，计算出所有可能的 $a$ 序列对应的 $b$ 序列中 $\sum_{i=1}^n b_i$ 的最小值。

输入格式

输入第一行两个非负整数 $n,m$，分别表示原始序列 $a$ 的长度及剩余元素的个数。

之后 $m$ 行，每行 $2$ 个数 $i,a_i$，表示一个剩余元素的位置和数值。

输出格式

输出一个整数表示可能的最小值。

5 3
4 0
3 7
5 0

7

提示

样例解释

已知的 $a$ 序列为：$X,X,7,0,0$，其中 $X$ 表示这个位置丢失了。一种可能的 $a$ 序列为 $0,7,7,0,0$，对应的 $b$ 序列为 $0,7,0,0,0$，和最小为 $7$。可以证明不存在和更小的情况。

::cute-table{tuack} |测试点编号|$n$|$m$|已知的 $a_i$| |:-:|:-:|:-:|:-:| |$1$|$n=2$|$m=1$|$0\le a_i\le 10^9$| |$2$|$1\le n\le10^9$|$m=0$|^| |$3$|$1\le n\le10^5$|$m=n$|^| |$4$|$1\le n\le5$|$0\le m\le n$|$0\le a_i\le 5$| |$5$|^|^|^| |$6$|$1\le n\le10^5$|^|$0\le a_i\le1$| |$7$|^|^|^| |$8$|^|^|$0\le a_i\le10$| |$9$|^|^|^| |$10$|^|^|^| |$11$|$1\le n\le10^9$|$0\le m\le\min\{n,10^5\}$|$0\le a_i\le1$| |$12$|^|^|^| |$13$|^|^|$0\le a_i\le10$| |$14$|^|^|^| |$16$|$1\le n\le10^6$|^|$0\le a_i\le10^9$| |$17$|^|^|^| |$18$|$1\le n\le10^9$|^|^| |$19$|^|^|^| |$20$|^|^|^|

注意未知的 $a_i$ 可以超过已知 $a_i$ 的范围。

保证输入中所有的 $i$ 不同，且满足 $1 \leq i \leq n$。

来自 CodePlus 2017 11 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。

Credit：idea/卢政荣 命题/卢政荣 验题/何昊天

Git Repo：https://git.thusaac.org/publish/CodePlus201711

感谢腾讯公司对此次比赛的支持。