You are given positive integers $N$ and $M$, along with $M$ pairs $(P_1,Q_1),(P_2,Q_2),\ldots,(P_M,Q_M)$, where $P_igood sequence if it satisfies both of the following conditions.

1. For every $1\le i\le N$, the indices of the elements among $A_1,A_2,\ldots,A_N$ that are multiples of $A_i$ form a single contiguous interval.

2. For every $1\le i\le M$, $A_{P_i}$ is not a multiple of $A_{Q_i}$.

The beauty of a good sequence is defined as the number of ordered pairs $(i,j)$ ($1\le i,j\le N$) such that $A_i$ is a multiple of $A_j$.

Determine whether a good sequence exists, and if it does, find the maximum possible beauty.

Input

The first line contains two integers $N$ and $M$, separated by a space. ($2\le N\le 100$; $1\le M\le 100$)

Each of the next $M$ lines contains two integers $P_i$ and $Q_i$, separated by a space. ($1\le P_i

Output

If no good sequence exists, print -1.

Otherwise, print the maximum possible beauty.

Examples

Example 1

Input

2 1
1 2

Output

3

Example 2

Input

4 1
2 3

Output

13

Example 3

Input

4 2
1 3
2 4

Output

12