Rezolvare PBinfo #4379

Cunoscutul “afacerist” din nuvela “Moara cu noroc”, Lică Sămădăul, a fost demascat pentru nenumăratele furturi pe care acesta le-a săvârșit. Din frică pentru ce urmează să apară, acesta s-a decis să fugă cât mai repede din sat. Satul poate fi reprezentat sub forma a N*M celule, organizate pe N linii (numerotate de la 1 la N) și M coloane (numerotate de la 1 la M). Fiecare celulă ca fi identificată prin coordonatele sale (i,j) (linia, respectiv coloana pe care se află celula). Casa lui Lică este în celula de coordonate (1,1), iar ieșirea din sat este în celula de coordonate (N, M).

Lică își ia toate obiectele de valoare din casă și se hotărăște să părăsească satul pe un cal. El are în grajd C cai frumoși. Fiecare cal i (1 ≤ i ≤ C) are o forță inițială f[i]. Orice cal se poate deplasa la un pas doar în una dintre celule învecinate (pe linie sau pe coloană). Fiecare celulă (i,j) (1 ≤ i ≤ N, 1 ≤ j ≤ M) are asociate două valori cu următoarea semnificație:

• a[i][j] – pentru ca Lică să poată intra în celula de coordonate (i,j), calul său trebuie să aibă în acel moment o forţă mai mare sau egală cu a[i][j];
• p[i][j] – în momentul ieşirii din celula de coordonate (i,j), calul lui Lică va pierde p[i][j] din forța sa.

Aceste valori vor fi reținute în două matrici, notate a, respectiv p.

Cerința

Cunoscându-se N și M, dimensiunile satului, C numărul cailor, forțele inițiale ale cailor și matricile a și p, să se determine numărul de cai pe care Lică îi poate utiliza astfel încât el să reușească să traverseze satul, de la casa lui până la ieșirea din sat.

Date de intrare

Fișierul de intrare moara.in conține pe prima linie numerele naturale N, M și C. Pe a doua linie se află C numere naturale reprezentând forțele inițiale ale cailor. Pe următoarele N linii se află câte M numere naturale, reprezentând elementele matricei a. Pe următoarele N linii se află câte M numere, reprezentând elementele matricei p. Valorile scrise pe aceeași linie vor fi separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire moara.out va conține o singură linie pe care va fi scris numărul cailor care au suficientă forță pentru a traversa satul, de la casa lui Lică până la ieșirea din sat.

Restricții și precizări

• 1 ≤ N, M ≤ 700
• 1 ≤ C ≤ 1.000.000
• Elementele matricelor a și p sunt numere naturale nenule ≤ 100.000
• Forțele cailor sunt numere naturale nenule ≤ 1.000.000.000

Exemplu:

moara.in

3 3 4
91 2 3 54
3 2 1
1 2 3
2 2 2
1 1 1
2 2 1
1 2 1

moara.out

2

Explicație

Lică poate traversa satul, respectând restricțiile impuse de enunț, doar pe primul și ultimul cal.