Elevators

A building has floors numbered from 1 to K and N elevators. Each elevator travels only between two distinct floors A and B, and it does not stop on any floor between them. Every elevator has the same speed: it takes 5 seconds to move by one floor.

At time 0, every elevator is at the lower of its two floors and immediately starts moving upward. When an elevator reaches its upper floor, it immediately starts moving downward; when it reaches its lower floor, it immediately starts moving upward again, and this repeats forever.

Mirko starts on floor 1 and wants to reach floor K as quickly as possible. He can transfer between elevators only on floors that are endpoints of both elevators. If the elevator he wants to transfer to is on that floor at that exact time, the transfer itself takes no time.

Compute the minimum number of seconds Mirko needs to reach floor K.

The first line contains two integers K and N: the number of floors and the number of elevators. (2 <= K <= 1000, 1 <= N <= 50000)

Each of the next N lines contains two integers A and B, describing one elevator that travels between floors A and B. (1 <= A < B <= K)

No two elevators travel between the same pair of floors. The input is guaranteed to allow Mirko to reach floor K.

Print one integer: the minimum number of seconds needed to travel from floor 1 to floor K.