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
Exemple
iepurasi.in
iepurasi.out
Explicaţie
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.