Revizia anterioară Revizia următoare
Fișierul intrare/ieșire | iepurasi.in, iepurasi.out | Sursă | Info-Oltenia 2010 |
---|---|---|---|
Autor | Robert-Mădălin Hasna | Vlad Duță | Adăugată de | Cristian Frâncu • francu |
Timp de execuție pe test | 0.4 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Iepurași (clasa a 8-a)
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ă tij secunde de la începutul jocului, apoi se ascunde iar; după alte tij secunde va apărea din nou, ș.a.m.d. Dacă Ancuța atinge acest iepuraș atunci când scoate capul afară va obține pij 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.
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.
Date de intrare
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 pij ș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 tij, reprezentând intervalul de timp la care apare iepurașul din gaura situată pe linia i și coloana j, exprimat în secunde.
Date de ieșire
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.
Restricții
- 1 ≤ N, M ≤ 500
- 1 ≤ D ≤ 10 000 000
- 1 ≤ pij ≤ 100, pentru 1≤ i ≤ N și 1 ≤ j ≤ M
- 1 ≤ tij ≤ 12, pentru 1 ≤ i ≤ N și 1 ≤ j ≤ M
Exemplu
iepurasi.in | iepurasi.out |
---|---|
This is some text written on multiple lines. |
This is another text written on multiple lines. |
Explicație
...