P4060 [Code+#1] Doable Problem

qmqmqm wants to give sublinekelzrip a doable problem. So he came up with this: given a non-negative integer sequence $a_i$ of length $n$, you need to compute its prefix XOR $b_i$, defined by $b_1=a_1,b_i=b_{i-1}\operatorname{xor}a_i(i \geq 2)$. However, due to a bug in the data generator, the sequence $a$ is very long, and because of insufficient memory, some $a_i$ were lost; only the elements at $m$ positions are known. Now qmqmqm asks you to, based on the remaining $a_i$, compute the minimum possible value of $\sum_{i=1}^n b_i$ among the $b$ sequences corresponding to all possible sequences $a$ consistent with the known entries.

The first line contains two non-negative integers $n, m$, denoting the length of the original sequence $a$ and the number of remaining known elements. Then follow $m$ lines. Each line contains two numbers $i, a_i$, indicating the position and value of a known element.

Output a single integer denoting the minimum possible value.

### Sample Explanation The known $a$ sequence is $X,X,7,0,0$, where $X$ means the entry is missing. One possible $a$ is $0,7,7,0,0$, whose corresponding $b$ is $0,7,0,0,0$, and the minimum sum is $7$. It can be proven that there is no smaller case. | Test point ID | $n$ | $m$ | Known $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$ | ^ | ^ | ^ | Note that unknown $a_i$ can exceed the range of the known $a_i$. It is guaranteed that all $i$ in the input are distinct and satisfy $1 \le i \le n$. From CodePlus 2017 November Contest, produced with honor by the Tsinghua University Department of Computer Science and Technology Student Algorithm and Competition Association. Credit: idea/Lu Zhengrong, problem setter/Lu Zhengrong, tester/He Haotian. Git Repo: https://git.thusaac.org/publish/CodePlus201711. Thanks to Tencent for supporting this contest. Translated by ChatGPT 5