#6251. 「CodePlus 2017 11 月赛」可做题

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

qmqmqm 希望给 sublinekelzrip 出一道可做题。于是他想到了这么一道题目:给一个长度为 nn 的非负整数序列 aia_i,你需要计算其异或前缀和 bib_i,满足条件 b1=a1b_1=a_1bi=bi1xorai(i2)b_i=b_{i-1} \mathbin{\mathrm{xor}} a_i \, (i \geq 2)

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

输入格式

输入第一行两个非负整数 nnmm,分别表示原始序列 aa 的长度及剩余元素的个数。

之后 mm 行,每行 22 个数 iiaia_i,表示一个剩余元素的位置和数值。

输出格式

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

样例

样例输入

5 3
4 0
3 7
5 0

样例输出

7

样例解释

已知的 aa 序列为:X,X,7,0,0X,X,7,0,0,其中 XX 表示这个位置丢失了。一种可能的 aa 序列为 0,7,7,0,00,7,7,0,0,对应的 bb 序列为 0,7,0,0,00,7,0,0,0,和最小为 77。可以证明不存在和更小的情况。

数据范围与提示

1n1091 \leq n \leq 10^90mmin{n,105}0 \leq m \leq \min\{n, 10^5\}0ai1090 \leq a_i \leq 10^9

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

保证输入中所有的 ii 不同,且满足 1in1 \leq i \leq n


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