Fişierul intrare/ieşire:iepurasi.in, iepurasi.outSursăInfo-Oltenia 2010
AutorRobert Madalin Hasna, Vlad DutaAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.4 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.iniepurasi.outExplicaţ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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici