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ā!
Teksta faila lifti.dat 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ē.
Teksta faila lifti.rez vienīgajā rindā jāizvada mazākais laiks sekundēs, pēc kurām Mirko var nokļūt augšstāvā.
| lifti.dat | lifti.rez |
10 4 1 5 5 10 5 7 7 10 |
45 |
| lifti.dat | lifti.rez |
10 3 1 5 3 5 3 10 |
105 |
| lifti.dat | lifti.rez |
20 5 1 7 7 20 4 7 4 10 10 20 |
150 |