Minimum Suffix Flips in a 6xP Matrix

You are given a 6 x P matrix A, where initially every element is 0 (zero). You are then provided with a set of requirements, each in the form of a pair \((i,j)\), where:

• \(1 \le i \le 6\) denotes the row index (1-indexed).
• \(1 \le j \le P\) denotes the column index (1-indexed).

For every requirement \((i,j)\), you must ensure that in row \(i\):

1. The cell \(A_{i,j}\) is 1.
2. Every cell to the right of \(j\), i.e. \(A_{i,j+k}\) for all \(k>0\) (if it exists), must be 0.

The only allowed operation is a suffix flip on a row. In a suffix flip you choose a row and an index \(k\) (\(1 \le k \le P\)), and flip the state (from 0 to 1 or from 1 to 0) of every cell from column \(k\) to column \(P\) in that row.

Initially, every row is in the 0 state. In order to meet the requirements, you may perform suffix flips on rows. Note that the operations on different rows are independent. For a row with a requirement at column \(j\):

• If \(j = P\), a single suffix flip at index \(P\) will set \(A_{i,P}\) to 1.
• If \(j < P\), a possible strategy is to flip at column \(j\) (this sets cells \(j\) to \(P\) to 1) and then flip at column \(j+1\) (this reverts cells \(j+1\) to \(P\) back to 0), resulting in \(A_{i,j} = 1\) and \(A_{i,j+1 \ldots P} = 0\).

Your task is to compute the minimum total number of suffix flip operations needed such that for every requirement \((i,j)\), the resulting row \(i\) satisfies:

[ A_{i,j} = 1 \quad \text{and} \quad \forall k > 0, ; A_{i,j+k} = 0. ]

</p>

Note: It is guaranteed that there will be at most one requirement per row. If a row has no requirement, no operation is needed on that row.

inputFormat

The first line of input contains two integers P and Q separated by a space, where P is the number of columns (\(1 \le P \le 10^5\)) and Q is the number of requirements. (Note that \(0 \le Q \le 6\))

Each of the next Q lines contains two integers i and j separated by a space, representing a requirement for cell \(A_{i,j}\) (1-indexed).

If Q is 0, then there are no further lines.

outputFormat

Output a single integer, the minimum total number of suffix flip operations required to satisfy all the requirements.

sample

5 2
1 3
4 5

3

</p>