## MELE3 - MELE3

 English Vietnamese

Tòa nhà có N thang máy. Mỗi thang máy nối đúng 2 tầng và mất 5s để đi qua 1 tầng

Bắt đầu, mỗi thang máy ở vị trí phía dưới và đi lên phía trên. Khi lên tới nơi, nó lại đi xuống và tiếp tục như thế.

Mirko ở tầng 1 và muốn lên đỉnh tòa nhà nhanh nhất, anh ta chỉ có thể thay đổi thang máy ở các tầng có thang máy chung và nếu lúc đó có một thang máy khác ở cùng tầng, anh ta không mất thời gian để chờ đợi thang máy.

Xác định thời gian nhỏ nhất để Mirko có thể lên được tầng cao nhất.

### Input

Dòng đầu là 2 số K và N,số tầng và số thang máy, 2 ≤ K ≤ 1000, 1 ≤ N ≤ 50000.

N dòng tiếp theo, mỗi dòng hai số nguyên A và B, 1 ≤ A < B ≤ K, mô tả thang máy nối 2 tầng A và B.

### Output

Tìm thời gian nhỏ nhất.

### Sample

```liftovi.in

10 4
1 5
5 10
5 7
7 10

liftovi.out

45

liftovi.in

10 3
1 5
3 5
3 10

liftovi.out

105

liftovi.in

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

liftovi.out

150

```

hide comments
 manishjoshi394: 2018-12-10 09:31:59 Just create a function that will calculate weights of the edges depending on the time already elapsed. Simple dijkstra. sherlock11: 2018-05-25 06:49:10 toughest part of question is to understand the question..........after reaching to a floor he can wait on that floor,the elevator don't need to be synchronous at the time for mirko to change the elevator.......this misunderstanding costed me 3 days and and raised question on my existence...finally i have answers for all the question.......by the way dijkstra with function to calculate wait time and there u go AC:) Last edit: 2018-05-25 06:49:59 badry atef: 2016-06-03 15:49:29 normal dijkstra's algorithm with binary search to calculate waiting time got it ACC :D xamitksx: 2016-04-08 19:27:13 NO STL is required . . variant of BFS ... marky: 2016-03-02 18:33:22 How to calculate wait time for next lift? Russo: 2015-11-09 00:40:26 --DO NOT-- read/write from/to the files indicated. Just ignore those lines of the input and read from stdin and write to stdout. Ankur Singh: 2015-06-22 08:02:56 can he change the elevator even when the elevator does not have a stoppage(begin / end) point. Like if one elevator goes from 1 - 5, other 3 - 5, can he change at floor 4 ? rush: 2015-03-19 18:42:59 Nice variation of a classical algorithm. Amitayush Thakur: 2014-09-02 18:05:32 My 100th submission on SPOJ :) Ninjaflyte: 2010-06-17 15:48:00 @~!(*(@*!@^& : I am completely sure that my program is correct, yet its getting WA. Can you check what's wrong? (or at least give a test case where it fails) Submission ID : 3740920

 Added by: ~!(*(@*!@^& Date: 2009-04-08 Time limit: 0.211s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ERL JS-RHINO NODEJS PERL6 VB.NET Resource: COI 03