Una dintre
cele mai importante functii din colonia de furnici este cea de ofiter de circulatie.
Motivul este ca in musuroiul de furnici exista un tunel foarte ingust, astfel
incat prin tunel nu pot sa treaca doua furnici una pe langa alta. Din fericire,
in tunel exista niste locuri speciale, unde furnicile pot sta si pot astepta
pana trec alte furnici. Furnicile pot trece una pe langa alta fara nici o problema
la capetele tunelului.
Ofiterul de circulatie cunoaste lungimea tunelului, precum si pozitiile locurilor speciale,
in care furnicile pot stationa. In fiecare dimineata ofiterul de serviciu primeste
o lista cu toate sosirile in tunel. Misiunea sa este de a organiza traficul
astfel incat toate furnicile sa poata traversa tunelul. Bineinteles ca acest
lucru poate fi realizat in multe moduri, mai rapid sau mai lent. Deoarece atunci
cand ultima furnica va iesi din tunel, ofiterul de serviciu isi poate incheia
programul, interesul sau este de a organiza traficul astfel incat acest lucru
sa se intample cat mai repede.
Orice furnica se deplaseaza cu 1cm/s. In locurile speciale pot astepta oricate furnici, iar
dimensiunile unui astfel de loc pot fi neglijate (poate fi considerat punctiform).
Cerinta
Scrieti un program care sa determine timpul minim necesar pentru ca toate furnicile
sa traverseze tunelul.
Date de intrare
Fisierul de intrare furnici.in contine
pe prima linie doua numere naturale D
si U, separate printr-un spatiu;
D reprezinta lungimea tunelului
exprimata in cm, iar U reprezinta
numarul de locuri speciale din tunel. Fiecare dintre urmatoarele U
linii contine pozitia unui loc special din tunel; pozitia este precizata prin
distanta fata de capatul din stanga al tunelului (exprimata in cm); pozitiile
sunt date in ordine de la stanga la dreapta. Pe urmatoarea linie se afla un
numar natural L, care reprezinta
numarul de furnici care intra prin capatul din stanga al tunelului. Fiecare
dintre urmatoarele L linii contine
timpul de sosire a unei furnici la capatul din stanga al tunelului. Pe urmatoarea
linie se afla un numar natural R,
care reprezinta numarul de furnici care intra prin capatul din dreapta al tunelului.
Fiecare dintre urmatoarele R
linii contine timpul de sosire a unei furnici la capatul din dreapta al tunelului.
Date de iesire
Fisierul
de iesire furnici.out contine
o singura linie pe care se afla timpul minim necesar pentru ca toate furnicile
sa traverseze tunelul, exprimat in secunde.
Restrictii
1 <= D <= 1000000
1 <= U, L, R <= 100000 (o suta de mii)
D > U
Timpii de sosire sunt exprimati in secunde si sunt numere naturale <= 2000000
(doua milioane)