qmqmqm 希望给 sublinekelzrip 出一道可做题。于是他想到了这么一道题目：给一个长度为 n 的非负整数序列 a_i，你需要计算其异或前缀和 b_i，满足条件 $b_1=a_1,bi=b{i-1} {xor}a_i(i \geq 2)$。
但是由于数据生成器出现了问题，他生成的序列 a 的长度特别长，并且由于内存空间不足，一部分 a_i 已经丢失了，只剩余 m 个位置的元素已知。现在 qmqmqm 找到你，希望你根据剩余的 $ai，计算出所有可能的 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 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
CodePlus