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

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

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

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

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

1≤n≤1091 \leq n \leq 10^91≤n≤109，0≤m≤min{n,105}0 \leq m \leq \min\{n, 10^5\}0≤m≤min{n,105}，0≤ai≤1090 \leq a_i \leq 10^90≤ai≤109

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

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

来自 CodePlus 2017 11 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit：idea/卢政荣　命题/卢政荣　验题/何昊天
Git Repo：https://git.thusaac.org/publish/CodePlus201711
感谢腾讯公司对此次比赛的支持。