Viens no visaugstāk novērtētajiem darbiem skudru pūznī ir satiksmes regulētājs. Tas tāpēc, ka šaurajās skudru pūžņa ejās divas pretī nākošas skudras nevar samainīties. Par laimi, ejās parasti mēdz būt paplašinājumi, kuros skudras var apstāties un palaist pretī nākošās skudras garām. Savukārt, eju galos skudras var netraucēti paiet viena otrai garām.
Satiksmes regulētājs zin ejas garumu, kā arī paplašinājumu atrašanās vietas. Katru rītu viņš saņem sarakstu ar skudru ierašanās laikiem ejas galos un viņa uzdevums ir organizēt kustību tā, lai visas skudras pēc iespējas īsākā laikā izietu pa eju.
Katras skudras ātrums ir 1 cm/s. Katrā paplašinājumā katrā brīdī var atrasties patvaļīgs skudru skaits.
Uzrakstiet programmu, kas nosaka īsāko laiku, kurā visas skudras būs šķērsojušas eju!
Teksta faila skudras.dat pirmajā rindā dotas divu naturālu skaitļu D (ejas garums centimetros) un U (paplašinājumu skaits ejā) vērtības, kas atdalītas ar tukšumsimbolu. Zināms, ka 1≤D≤1000000, 1≤U≤100000, D>U.
Nākošajās U faila rindās dotas paplašinājumu atrašanās vietas, sākot no kreisās puses kā attālumi no ejas gala centimetros.
Nākošajā faila rindā dota naturāla skaitļa L (skudru skaits, kas ierodas pie ejas kreisā gala, 1 ≤L≤100000) vērtība. Nākošajās L rindās doti katras skudras ierašanās laiki pie ejas kreisā gala - pa vienam laikam katrā rindā.
Nākošajā faila rindā dota naturāla skaitļa R (skudru skaits, kas ierodas pie ejas labā gala, 1 ≤R≤100000) vērtība. Nākošajās R rindās doti katras skudras ierašanās laiki pie ejas labā gala - pa vienam laikam katrā rindā.
Laiku apzīmē ar veselu nenegatīvu skaitli kā nobīdi sekundēs no kāda fiksēta laika momenta 0. Šī vērtība atrodas robežās no 0 līdz 2000000.
Teksta faila skudras.rez vienīgajā rindā jāizvada viens naturāls skaitlis - mazākais laiks sekundēs, kurā visas skudras var iziet pa eju.
| skudras.dat | skudras.rez |
5 1 2 1 3 1 2 |
8 |
| skudras.dat | skudras.rez |
10 1 3 1 0 1 2 |
16 |
| skudras.dat | skudras.rez |
10 2 4 6 2 0 4 1 0 |
14 |