엘리베이터

한 건물에는 1층부터 K층까지 있고, N개의 엘리베이터가 있다. 각 엘리베이터는 서로 다른 두 층 A와 B만 오가며, 그 사이의 층에는 서지 않는다. 모든 엘리베이터의 속도는 한 층을 지나는 데 5초로 같다.

처음 시각 0에는 모든 엘리베이터가 자신이 오가는 두 층 중 낮은 층에 있으며, 곧바로 높은 층을 향해 출발한다. 엘리베이터가 높은 층에 도착하면 즉시 낮은 층으로 내려가고, 낮은 층에 도착하면 다시 즉시 올라가며 이 움직임을 반복한다.

미르코는 처음에 1층에 있고, 가능한 한 빨리 K층에 도착하려고 한다. 두 엘리베이터가 같은 층을 정차 층으로 공유하고, 갈아타려는 엘리베이터가 그 순간 그 층에 있다면, 미르코는 시간을 들이지 않고 갈아탈 수 있다.

미르코가 K층에 도착하는 데 필요한 최소 시간을 초 단위로 구하라.

첫째 줄에 층수 K와 엘리베이터 수 N이 공백으로 구분되어 주어진다. (2 <= K <= 1000, 1 <= N <= 50000)

다음 N개의 줄에는 각 엘리베이터가 오가는 두 층 A와 B가 공백으로 구분되어 주어진다. (1 <= A < B <= K)

같은 두 층을 오가는 엘리베이터는 둘 이상 주어지지 않는다. 항상 K층에 도착할 수 있는 입력만 주어진다.

1층에서 K층까지 가는 데 필요한 최소 시간을 초 단위로 한 줄에 출력한다.