Fișierul intrare/ieșire	goldmine.in, goldmine.out	Sursă	Simulare OJI Clasa a 9-a
Autor	Teodor Plop	Adăugată de	Teodor Plop • teodor94
Timp de execuție pe test	0.2 sec	Limită de memorie	4096 KB
Scorul tău	N/A	Dificultate	1

Vezi soluțiile trimise | Statistici

Gold Mine (clasa a 9-a)

Se dă o hartă a unei mine de aur sub forma unei matrice cu N linii și M coloane:

• Fiecare element A[i][j] reprezintă cantitatea de aur care poate fi extrasă din acea zonă.
• Liniile reprezintă adâncimea (linia 1 este la suprafață, linia N este cel mai adânc).

Se primesc Q contracte de tipul (K, H). Pentru fiecare contract, trebuie să răspundem care este cantitatea maximă de aur pe care o putem excava dacă folosim K excavatoare care pot ajunge până la adâncime maxim H? Fiecare excavator poate fi folosit pentru o singură coloană!

Date de intrare

Fișierul de intrare goldmine.in conține pe prima linie numerele naturale N, M și Q. Pe următoarele N linii se găsesc câte M numere naturale, reprezentarea minei de aur. Pe următoarele Q linii se găsesc câte două numere naturale K și H, datele de contract.

Date de ieșire

Fișierul de ieșire goldmine.out va conține Q linii, pe fiecare linie aflându-se răspunsul la câte un contract.

Restricții

• 1 ≤ N, M ≤ 500
• 1 ≤ A[i, j] ≤ 1.000
• 1 ≤ Q ≤ 200.000
• 1 ≤ K ≤ M
• 1 ≤ H ≤ N

Exemplu

goldmine.in	goldmine.out	Explicație
3 4 3 2 1 5 3 4 2 6 1 1 8 1 5 2 1 3 2 1 3	8 21 12	8 = (5) + (3) 21 = (5 + 6) + (4 + 2) + (3 + 1) 12 = (5 + 6 + 1)