Description

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.

Input Format

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 Format

Output a single integer denoting the minimum possible value.

5 3
4 0
3 7
5 0

7

Hint

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.

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