Nosaukums
Lifti (lifti)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
67%

Definīcija

Daudzstāvu namam ir K stāvi un namā ir N lifti. Katrs lifts savieno tieši divus stāvus un neapstājas starp stāviem. Visu liftu ātrums ir vienāds - katrs lifts vienu stāvu veic 5 sekundēs. Sākuma momentā lifts atrodas zemākajā no abiem stāviem un sāk kustību augšup. Kad lifts nonāk augšējā stāvā, tas nekavējoties sāk kustību atpakaļ uz leju. Kad atkal nonācis zemākajā stāvā, tas nekavējoties sāk atkal kustību aušup, utt. Mirko atrodas pirmajā(pašā zemākajā) stāvā un vēlas nokļūt cik ātri vien iespējams nama augšējā stāvā. Viņš var pārkāpt no viena lifta otrā tikai tad, ja šajā stāvā apstājas abi lifti. Ja vienā un tajā pašā brīdī abi lifti atrodas šajā stāvā, tad pāriešana no viena lifta uz otru laiku neprasa.

Uzrakstiet programmu, kas nosaka ātrākais pēc cik sekundēm Mirko var nokļūt augšējā stāvā!


Ievaddatu raksturojums

Ievaddatu pirmajā rindā doti divi naturāli skaitļi K(nama stāvu skaits) un N (liftu skaits), kas atdalīti ar tukšumsimbolu. Zināms, ka 2≤K≤1000 un 1≤N≤50000. Katrā no nākošajām N faila rindām dots pa viena lifta aprakstam. Katrā no šīm rindām doti divi naturāli skaitļi A un B, kas atdalīti ar tukšumsimbolu. Zimnāms, ka 1≤A<B≤K un šie skaitļi norāda stāvus, starp kuriem kursē attiecīgais lifts. Divi dažādi lifti nekursē starp vienu un to pašu stāvu pāri. Ievaddati ir tādi, ka atrisinājums eksistē.


Izvaddatu raksturojums

Izvaddatu vienīgajā rindā jāizvada mazākais laiks sekundēs, pēc kurām Mirko var nokļūt augšstāvā.


Piezīmes

Uzdevums izmantots Horvātijas informātikas olimpiādē 2003.gadā


Paraugdati

Stdin
10 4
1 5
5 10
5 7
7 10
Stdout
45

Stdin
10 3
1 5
3 5
3 10
Stdout
105

Stdin
20 5
1 7
7 20
4 7
4 10
10 20
Stdout
150

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.