MELE3 - MELE3

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mele3


Tòa nhà có N thang máy. Mỗi thang máy nối đúng 2 tầng và mất 5s để đi qua 1 tầng

Bắt đầu, mỗi thang máy ở vị trí phía dưới và đi lên phía trên. Khi lên tới nơi, nó lại đi xuống và tiếp tục như thế.

Mirko ở tầng 1 và muốn lên đỉnh tòa nhà nhanh nhất, anh ta chỉ có thể thay đổi thang máy ở các tầng có thang máy chung và nếu lúc đó có một thang máy khác ở cùng tầng, anh ta không mất thời gian để chờ đợi thang máy.

Xác định thời gian nhỏ nhất để Mirko có thể lên được tầng cao nhất.

Input

Dòng đầu là 2 số K và N,số tầng và số thang máy, 2 ≤ K ≤ 1000, 1 ≤ N ≤ 50000.

N dòng tiếp theo, mỗi dòng hai số nguyên A và B, 1 ≤ A < B ≤ K, mô tả thang máy nối 2 tầng A và B.

Output

Tìm thời gian nhỏ nhất.

Sample

Input: 
10 4 
1 5 
5 10 
5 7 
7 10 
 
Output:
45 
Input:
 10 3 
1 5 
3 5 
3 10 
 
Output:
105
Input: 
20 5 
1 7 
7 20 
4 7 
4 10 
10 20 
 
Output:
150 

Được gửi lên bởi:psetter
Ngày:2009-04-08
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:COI 03

hide comments
2016-05-08 17:14:50 Nguyen Cuong
6 hit mới AC ._. bị sai công thức mà cứ tưởng là thang máy nào đến sớm nhất thì nhảy lên ._.
2014-12-31 14:48:40 [$Zeus$]
Dijkstra Heap.
2014-11-22 08:36:21 Tây Cuồng
Bài này hay quá :))
2014-11-22 01:55:04 John and the cows
thang máy di chuyển liên tục
2014-07-02 05:02:11 _sanghk11_
bài này dùng dijkstra được ko moi ng............



Last edit: 2014-07-02 05:19:57
2014-01-27 12:46:22  
Em không hiểu đề, ai giải thích giúp với...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.