양의 정수 $N$, $M$과 $M$개의 쌍 $(P_1,Q_1),(P_2,Q_2),\ldots,(P_M,Q_M)$이 주어진다. 이때 $P_i좋은 수열이라고 한다.

1. 모든 $1\le i\le N$에 대하여, $A_1,A_2,\ldots,A_N$ 중 $A_i$의 배수인 원소들은 하나의 연속된 구간을 이룬다.

2. 모든 $1\le i\le M$에 대하여, $A_{P_i}$는 $A_{Q_i}$의 배수가 아니다.

좋은 수열의 아름다움은 $A_i$가 $A_j$의 배수인 순서쌍 $(i,j)$ ($1\le i,j\le N$)의 개수로 정의된다.

좋은 수열이 존재하는지 판별하고, 존재한다면 아름다움의 최댓값을 구하여라.

입력

첫째 줄에 정수 $N$, $M$이 공백을 사이에 두고 주어진다. ($2\le N\le 100$; $1\le M\le 100$)

다음 $M$개의 줄에 걸쳐 정수 $P_i$, $Q_i$가 공백으로 구분되어 주어진다. ($1\le P_i

출력

좋은 수열이 존재하지 않으면 -1을 출력한다. 존재한다면 아름다움의 최댓값을 출력한다.

입출력 예시

예시 1

입력

2 1
1 2

출력

3

예시 2

입력

4 1
2 3

출력

13

예시 3

입력

4 2
1 3
2 4

출력

12