== include(page="template/taskheader" task_id="morcovi") ==
Poveste si cerinta...
Fermierul Ion are o gradina formata din $N$ zone patratice cu latura de $1$ metru, asezate una dupa alta, in linie. In fiecare astfel de zona creste cate un morcov magic. Pentru fiecare morcov este cunoscuta valoarea sa energetica. Rila Iepurila, iepurele buclucas, a invadat gradina fermierului si a inceput sa manance morcovii. Iepurasul urmeaza un anumit traseu si mananca integral morcovii din zonele prin care trece. Dupa ce un morcov este mancat, creste altul in loc, de aceeasi valoare energetica (nu uitati ca morcovii sunt magici iar gradina este una imaginara). Gradul de satisfactie al lui Rila este dat de suma valorilor energetice ale morcovilor pe care ii mananca.
Pentru ca iepurele este un animal destept, traseul acestuia are anumite caracteristici. Rila incepe dintr-o zona oarecare si executa un numar $P$ de salturi iepuresti, astfel incat prin salturile sale sa nu paraseasca niciodata gradina. Fermierul, dupa ce a studiat comportamentul iepurelui pentru o perioada lunga de timp, cunoaste acum lungimile celor $P$ salturi ale iepurelui si stie ca acesta executa toate aceste salturi intr-o ordine oarecare.
Sa se determine gradul de satisfactie maxim pe care il poate obtine iepurele.
h2. Date de intrare
Fisierul de intrare $morcovi.in$ ...
Fisierul de intrare $morcovi.in$ contine pe prima linie {$N$}, numarul de zone ale gradinii. Pe a doua linie din fisier se gasesc $N$ numere naturale, al $i$-lea numar de pe aceasta linie indicand valoarea energetica a morcovilor ce cresc in zona a $i$-a. Cea de a treia linie din fisier contine numarul {$P$}, numarul de salturi pe care le face iepurele. Ultima linie contine $P$ numere naturale, intr-o ordine oarecare, indicand lungimile salturilor iepurelui.
h2. Date de iesire
In fisierul de iesire $morcovi.out$ ...
Pe prima linie a fisierului de iesire $morcovi.out$ se gaseste un singur numar natural, reprezentand gradul maxim de satisfactie ce poate fi obtinut de iepurele Rila in traseul sau prin gradina fermierului.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 1 000$
* $1 ≤ P ≤ 12$
* Valoarea energetica a unui morcov este un numar natural din intervalul {$[1, 100 000 000]$}
* Fiecare lungime din cele $P$ este mai mica decat $N$
* Un salt din zona $x$ in zona $y$ are lungimea {$|x-y|$}
h2. Exemplu
table(example). |_. morcovi.in |_. morcovi.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
|7
1 20 3 1 1 40 10
3
1 2 4
|71|
h3. Explicatie
...
Iepurele porneste din casuta {$4$}. De acolo executa un salt de lungime $2$ spre stanga, pana in casuta cu morcovul de valoare {$20$}. Apoi executa pe rand salturile de lungime $4$ si $1$ spre dreapta, mancand si morcovii cu valorile {$40$} si {$10$}. Gradul de satisfactie este {$1+20+40+10 = 71$}.
== include(page="template/taskfooter" task_id="morcovi") ==
