Maximizing Adjacent Sum Pairs in Wooden Stick Arrangements

You are given some wooden sticks. Each stick has two numbers: a left number and a right number. Both numbers are natural numbers in the range ( [0,c) ) (i.e. from 0 to (c-1)). You need to arrange all the sticks in a sequence (a permutation of the sticks) so that the number of adjacent pairs (i.e. the pair formed by the right number of a stick and the left number of the next stick) whose sum equals ( c ) is maximized.

For example, let ( c = 3 ) and you have two sticks: one stick is 1 - 2 and the other is 1 - 0. If you arrange them as 1 - 0, 1 - 2, the only adjacent pair has numbers (0) and (1) with sum (1), which is not equal to (3). However, if you arrange them as 1 - 2, 1 - 0, the touching numbers are (2) and (1) and their sum is (3); hence you get one pair whose sum equals (3).

Your task is to compute the maximum possible number of adjacent pairs whose sum equals ( c ) when the sticks are arranged optimally. Note that although every arrangement uses all sticks, only the adjacent pairs in the chosen permutation can contribute to the total count (and there are (n-1) such pairs if there are ( n ) sticks).

inputFormat

The input begins with a line containing two integers ( c ) and ( n ) (with ( c > 0 ) and ( n \ge 1 )). Each of the following ( n ) lines contains two integers representing the left and right numbers on a wooden stick. All numbers lie in the range ( [0, c) ).

outputFormat

Output a single integer representing the maximum possible number of adjacent pairs whose sum equals ( c ) in an optimal arrangement of the wooden sticks.

sample

3 2
1 2
1 0

1