시스템에는 $1$부터 $n$까지 번호가 매겨진 $n$가지 프로그램 유형이 있다. 유형 $k$인 프로그램의 인스턴스가 시작되면 $k$초마다 로그 항목을 생성한다. 구체적으로, 시작 시각을 기준으로 $k,2k,3k,\ldots$ 시점에 로그를 생성한다.

시각 $0$에 시스템은 $m$개의 명령을 동시에 실행한다. $i$번째 명령은 번호가 구간 $[l_i,r_i]$에 속하는 각 프로그램 유형의 인스턴스를 하나씩 시작한다. 여러 명령의 구간이 겹치면 같은 프로그램 유형의 인스턴스가 여러 개 시작될 수 있으며, 각 인스턴스는 독립적으로 로그를 생성한다는 점에 유의하라.

시스템은 시각 $1,2,\ldots,n$에 생성된 모든 로그 항목을 기록한다. 각 기록에는 해당 로그를 생성한 인스턴스의 프로그램 유형 번호만 들어 있다.

이 로그들을 압축하는 알고리즘을 설계해야 한다. 모든 $n$가지 프로그램 유형에 비어 있지 않은 이진 문자열을 식별자로 할당하되, 어떤 식별자도 다른 식별자의 접두사가 되지 않도록 해야 한다. 기록 하나를 인코딩하는 비용은 해당 프로그램 유형에 할당된 식별자의 길이이며, 총비용은 모든 기록의 비용을 합한 값이다. 가능한 최소 총비용을 구하라.

입력

첫 번째 줄에 두 정수 $n,m$ ($1\le n\le 10^{10}$, $1\le m\le 10^5$)이 주어진다. 각각 프로그램 유형의 수와 명령의 수를 나타낸다.

다음 $m$개의 줄에는 각각 두 정수 $l_i,r_i$ ($1\le l_i\le r_i\le n$)가 주어지며, 시작 명령을 나타낸다.

출력

최소 총비용을 나타내는 정수 하나를 출력하라.

예제

입력 1

5 1
1 5

출력 1

20

입력 2

6 2
1 3
4 6

출력 2

32

참고

로그는 시간순으로 기록된다고 가정하자. 같은 시각에 생성된 로그의 기록은 해당 프로그램 유형의 번호가 비내림차순이 되도록 정렬된다.

첫 번째 예제에서 로그는 $[1,1,2,1,3,1,2,4,1,5]$이다. 최적의 식별자 할당 중 하나는 (프로그램 $1$: 0, 프로그램 $2$: 100, 프로그램 $3$: 101, 프로그램 $4$: 110, 프로그램 $5$: 111)이다. 비용은 $5\times 1+2\times 3+1\times 3+1\times 3+1\times 3=20$이다.

두 번째 예제에서 로그는 $[1,1,2,1,3,1,2,4,1,5,1,2,3,6]$이다. 최적의 식별자 할당 중 하나는 (프로그램 $1$: 0, 프로그램 $2$: 10, 프로그램 $3$: 1100, 프로그램 $4$: 1101, 프로그램 $5$: 1110, 프로그램 $6$: 1111)이다. 비용은 $6\times 1+3\times 2+2\times 4+1\times 4+1\times 4+1\times 4=32$이다.