lift

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 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

Timp maxim de executie/test: 1.2 secunde.

prof. Emanuela Cerchez

Liceul de Informatica "Grigore Moisil" Iasi

Contact:ema at mail.dntis.ro