Vasile locuieste intr-o cladire cu K
etaje (numerotate de la 1
la K, incepând
de jos in sus) si in care exista N
lifturi. Fiecare lift face legatura intre exact doua etaje ale cladirii si nu
se opreste la etajele dintre acestea. Toate lifturile circula cu aceeasi viteza,
fiind necesare 5 secunde pentru a trece de un etaj.
Initial, fiecare lift se gaseste la etajul sau cel mai de jos si incepe sa
se miste in sus. Când un lift ajunge la etajul sau de sus, usa liftului
se deschide, apoi imediat incepe sa coboare pâna la etajul sau de jos,
când iarasi usa liftului se deschide, dupa care liftul incepe sa urce,
s.a.m.d.
Vasile se afla la etajul 1
al cladirii si doreste sa ajunga cât mai repede la etajul K.
El poate trece de la un lift la altul numai la un etaj comun celor doua
lifturi (unde lifturile au usa deschisa) si schimbarea liftului nu necesita
timp suplimentar, daca liftul respectiv se afla la acel etaj.
Cerinta
Scrieti un program care sa determine timpul minim in care Vasile poate ajunge la ultimul
etaj al cladirii.
Date de intrare
Prima linie a fisierului de intrare lift.in
contine doua numere naturale K
si N, separate printr-un
spatiu, reprezentând numarul de etaje ale cladirii si respectiv numarul
de lifturi. Fiecare dintre urmatoarele N linii contine descrierea unui lift sub forma a doua numere naturale A
si B, separate printr-un
spatiu, semnificând ca liftul circula intre etajele A
si B (1<=A<B<=K).
Date de iesire
Fisierul de iesire lift.out
contine o singura linie pe care se afla timpul minim (exprimat in secunde) in
care Vasile poate ajunge la ultimul etaj.
Restrictii
2 <= K <= 1000
1 <= N <= 50000
Nu exista doua lifturi care sa circule intre aceleasi doua etaje.
Pentru datele de test exista intotdeauna solutie.
Exemple
lift.in
lift.out
lift.in
lift.out
lift.in
lift.out
10 4
1 5
5 10
5 7
7 10
45
10 3
1 5
3 5
3 10
105
20 5
1 7
7 20
4 7
4 10
10 20
150
prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil"
Iasi