시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 5 0 0 0.000%

문제

솔리테어에는 N 개의 엘리베이터가 있습니다. 각 엘리베이터는 정확하게 2 개 층을 연결하며 두 층 사이의 층에서는 멈추지 않습니다. 모든 엘리베이터의 속도는 같으며 한 층을 통과하는 데 5 초가 걸립니다.

처음에는 각 엘리베이터가 낮은 위치에 있으며 상부 층으로 순항하기 시작합니다. 어떤 엘리베이터가 위쪽 위치에 오면 바로 아래쪽 위치로 돌아 가기 시작합니다.

미르코는 가장 낮은 1층에 있으며 가능한 한 빨리 솔리테어의 꼭대기에 오고 싶어합니다. 그는 두 엘리베이터가 같은 층에서 멈출 때만 갈아탈 수 있으며, 도착한 순간에 다른 엘리베이터가 있다면 갈아타는 데 시간이 걸리지 않습니다.

미르코가 솔리테어의 맨 위로 갈 수있는 최소 시간을 계산하는 프로그램을 작성하십시오.

입력

입력 파일의 첫 번째 줄에는 공백으로 분리 된 두 개의 정수 K와 N이 있으며 솔리테어의 층수와 엘리베이터의 수입니다. 2 ≤ K ≤ 1000, 1 ≤ N ≤ 50000입니다.

다음 N 개의 줄에는 각각 하나의 엘리베이터에 대한 설명이 있으며, 공백으로 분리된 두 개의 정수 A와 B는 엘리베이터가 A 층과 B층 사이를 이동한다는 것을 의미합니다. 1 ≤ A < B ≤ K입니다.

같은 층 사이를 이동하는 두 개의 다른 엘리베이터는 없습니다.

참고 : 입력 데이터는 솔루션이 항상 존재 함을 보장합니다.

출력

출력 파일의 유일한 행에서 위의 텍스트에서 최소 시간 (초 단위)을 작성하십시오.

예제 입력

10 4
1 5
5 10
5 7
7 10

예제 출력

45

예제 입력 2

10 3
1 5
3 5
3 10

예제 출력 2

105

예제 입력 3

20 5
1 7
7 20
4 7
4 10
10 20

예제 출력 3

150

힌트

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2003 > Regional Competition - Juniors 4번