Fișierul intrare/ieșire furnici.in, furnici.out Sursă .campion 2003
Autor Marinel Șerban Adăugată de avatar andrei20003 Ionescu Andrei andrei20003
Timp de execuție pe test 0.2 sec Limită de memorie 15364 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

Furnici

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 ieșire

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.

Restricții

  • 1 ≤ D ≤ 1000000
  • 1 ≤ U ≤ 100000
  • 1 ≤ L ≤ 100000
  • 1 ≤ R ≤ 100000

Exemplu

furnici.in furnici.out
5 1
2
1
3
1
2
8
10 1
3
1
0
1
2
16
10 2
4
6
2
0
4
1
0
14

Trebuie să te autentifici pentru a trimite soluții. Click aici