morcovi

Morcovi

== include(page="template/taskheader" task_id="morcovi") ==

Fermierul John 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.

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 precum si numarul posibil de trasee cu acest grad maxim.

Sa se determine gradul de satisfactie maxim pe care il poate obtine iepurele.

h2. Date de intrare

h2. Date de iesire

Fisierul de iesire $morcovi.out$ conine o singura linie pe care se gasesc doua numere naturale. Primul numar reprezinta gradul maxim de satisfactie ce poate fi obtinut de iepurele Rila, iar cel de-al doilea numarul de trasee distincte in urma carora se obtine acest grad maxim.

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$

* 80% din teste au $P ≤ 7$

* 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|$}

1 20 3 1 1 40 10
3
1 2 4

|71 1|

|71|

h3. Explicatie

3892