题目描述

qmqmqm希望给sublinekelzrip出一道可做题。于是他想到了这么一道题目：给一个长度为$n$的非负整数序列$a_i$,你需要计算其异或前缀和$b_i$,满足条件$b_1=a_1$,$b_i=b_{i-1}\ 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$。可以证明不存在和更小的情况。

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

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

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

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

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

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