Minimizing the Sum of XOR Prefixes

Consider a sequence \(a_1,a_2,\dots,a_n\) of nonnegative integers of length \(n\). Its XOR prefix sum \(b_1,b_2,\dots,b_n\) is defined by the recurrence:

\(b_1 = a_1\) and \(b_i = b_{i-1}\ \oplus\ a_i\) for \(i \ge 2\),

where \(\oplus\) denotes the bitwise XOR operation. Due to a data generator error, the original sequence \(a\) is extremely long and most of its elements have been lost; only \(m\) elements at specified positions remain known. More precisely, you are given \(m\) pairs \((i, a_i)\) indicating that the \(i^{th}\) element of \(a\) equals \(a_i\). For all other positions, you are allowed to assign an arbitrary nonnegative integer.

Your task is to determine, over all sequences \(a\) consistent with the given information, the minimum possible value of the sum \[ S = \sum_{i=1}^{n} b_i, \] where the \(b_i\)'s are defined as above.

Note: When there is freedom to choose the missing values, you can choose them in such a way as to "reset" the XOR prefix to minimize the sum. In particular, if a missing element is followed by a known one, you may choose the preceding missing value to minimize the known element's contribution.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq m \leq n)\) where \(n\) is the length of the sequence and \(m\) is the number of known elements.

The next \(m\) lines each contain two integers \(i\) and \(v\) (with \(1 \le i \le n\) and \(v \ge 0\)), indicating that \(a_i = v\). The positions may be given in arbitrary order. For positions not mentioned in the input, you can assign any nonnegative integer.

If \(m = 0\), then no elements are known and you are free to choose the entire sequence.

outputFormat

Output a single integer representing the minimum possible value of \(S = \sum_{i=1}^{n} b_i\) over all sequences \(a\) consistent with the input.

sample

5 3
1 3
3 5
5 4

12