== include(page="template/taskheader" task_id="iepurasi") ==
Poveste și cerință...
De ziua Ancuței mama sa a dus-o la o sală de jocuri. Ea a fost foarte entuziasmată de un aparat care avea $NxM$ găuri dispuse pe $N$ linii (numerotate de la $1$ la [$N$]) și $M$ coloane (numerotate de la $1$ la [$M$]). Din fiecare gaură, la un anumit interval de timp scoate capul un iepuraș. Dacă Ancuța atinge iepurașul exact atunci când el iese din gaură ea obține un anumit număr de puncte.
Mai exact, iepurașul situat în gaura de pe linia $i$ și coloana $j$ va scoate capul după $t[~ij~]$ secunde de la începutul jocului, apoi se ascunde iar; după alte $t[~ij~]$ secunde va apărea din nou, ș.a.m.d. Dacă Ancuța atinge acest iepuraș atunci când scoate capul afară va obține $p[~ij~]$ puncte.
Iepurașul scoate capul din gaură și se ascunde iar instantaneu. Deci în momentul respectiv Ancuța poate atinge un singur iepuraș.
Scopul jocului este de a aduna cât mai multe puncte.
h2. Cerință
Scrieți un program care să calculeze numărul maxim de puncte pe care Ancuța le poate aduna în $D$ secunde de joc, știind că ea joacă optim.
h2. Date de intrare
Fișierul de intrare $iepurasi.in$ ...
Fișierul de intrare $iepurasi.in$ conține pe prima linie 3 numere naturale separate prin spații $N M D$, cu semnificația din enunț. Pe următoarele $N$ linii se află câte $M$ numere naturale separate prin spații; a [$j$]-a valoare de pe a [$i$]-a linie dintre acestea este $p[~ij~]$ și reprezintă numărul de puncte pe care Ancuța îl obține dacă atinge iepurașul din gaura situată pe linia $i$ și coloana [$j$].
Pe următoarele $N$ linii se află tot câte $M$ numere naturale separate prin spații; a [$j$]-a valoare de pe a [$i$]-a linie dintre acestea este $t[~ij~]$, reprezentând intervalul de timp la care apare iepurașul din gaura situată pe linia $i$ și coloana [$j$], exprimat în secunde.
h2. Date de ieșire
În fișierul de ieșire $iepurasi.out$ ...
Fișierul de ieșire $iepurasi.out$ va conține o singură linie pe care va fi scris numărul maxim de puncte care pot fi adunate în cele $D$ secunde.
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ N, M ≤ 500$
* $1 ≤ D ≤ 10 000 000$
* $1 ≤ p[~ij~] ≤ 100$, pentru $1≤ i ≤ N$ și $1 ≤ j ≤ M$
* $1 ≤ t[~ij~] ≤ 12$, pentru $1 ≤ i ≤ N$ și $1 ≤ j ≤ M$
h2. Exemplu
table(example).
|_. iepurasi.in |_. iepurasi.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
|_. iepurasi.in |_. iepurasi.out |_. Explicații |
| 2 4 6
5 6 1 100
7 2 4 9
2 5 4 9
9 3 7 6
| 27
| Sunt 8 găuri, dispuse în 2 linii și 4 coloane. Ancuța se joacă 6 secunde.
In secunda 2 apare iepurașul din gaura de pe linia 1 și coloana 1, Ancuța îl
atinge și obține 5 puncte.
În secunda 3 apare iepurașul de pe linia 2, coloana 2, Ancuța îl atinge și
obține 2 puncte.
În secunda 4 vor apărea 2 iepurași (cel de pe linia 1, coloana 1 și cel de pe
linia 1 coloana 3). Ancuța îl atinge pe cel de pe linia 1 coloana 1 obținând
5 puncte.
În secunda 5 apare iepurașul de pe linia 1 coloana 2, Ancuța îl atinge și
obține 6 puncte.
În secunda 6 apar 3 iepurași (cel de pe linia 1, coloana 1; cel de pe linia 2
coloana 2 și cel de pe linia 2 coloana 4). Ancuța îl atinge pe cel de-al treilea
și obține 9 puncte.
Total: 5+2+5+6+9=27.
|
== include(page="template/taskfooter" task_id="iepurasi") ==
== include(page="template/taskfooter" task_id="iepurasi") ==
