Moving Paintings

In his free time, Giorgio likes to go look at paintings. He’s actually not really into fancy Louvre level stuff; in fact, he doesn’t even need the paintings to be real paintings: any sequence of rectangular frames on a wall is OK for him, as long as they are in the right order!

Today, Giorgio noticed that one of the walls in his university has a long sequence of paintings (mixed with “Best Paper Award” certificates), but he thinks that the heights are just too random, and he wants to fix that.

Each painting can be seen as an $A \cdot B$ rectangle, which can be rotated at will.

Giorgio wants the sequence of paintings to respect a simple height property: for a given height value $H$, decided by Giorgio, the sequence should be made of two concatenated sequences:

• The first part of the sequence only has paintings shorter than $H$.
• The second part of the sequence only has paintings taller than $H$.

Notice that Giorgio will choose an H value which is different from every rectangle’s $A$ and $B$ dimensions. To realize the height property, Giorgio will start by rotating the paintings (thus exchanging the $A$ and $B$ dimensions). Giorgio can rotate any number of paintings he wants, because he makes the rules.

After the “rotation phase”, it’s not guaranteed that the height property is respected. To solve this, Giorgio will actually move the paintings around: he will repeatedly choose two paintings and swap them. In the end, the sequence will be reordered and Giorgio will be happy.

Rotating paintings is easy, but moving them is very hard: some paintings can be quite heavy! Help Giorgio compute the minimum number of swaps needed to reorder the sequence.

Input data

The first line contains integer $H$. The second line contains integer $N$. The next $N$ lines contain two integers each: the dimensions $A_i$ and $B_i$ of the $i$-th painting.

Output data

You need to write a single line with an integer: the minimum number of swaps.

Constraints and clarifications

• $1 \leq H \leq 1 \ 000 \ 000 \ 000$.
• $1 \leq N \leq 1 \ 000 \ 000$.
• $1 \leq A_i, B_i \leq 1 \ 000 \ 000 \ 000$ for each $i = 0 \dots N − 1$.
• $A_i \neq H$ and $B_i \neq H$ for each $i = 0 \dots N - 1$.

Example 1

stdin

10
3
20 19
2 2
17 15

stdout

1

Explanation

In the first sample case Giorgio can just swap the first two paintings. After that, the sequence will be made of two parts: the first painting being shorter than $H$ and the last two paintings being taller.

Example 2

stdin

10
5
11 13
4 15
12 14
9 7
5 8

stdout

2

Explanation

In the second sample case a possible solution for Giorgio is to rotate the second painting ($4 \cdot 15$ becomes $15 \cdot 4$). After that he can swap the first and last paintings, and then swap the second-to-last and the third-to-last paintings. In the end, the sequence will be made of two parts: the first $3$ paintings being shorter than $H$, the last $2$ being taller.