Problem 3257: Ants in the Matrix

Cerință

Într-o zi frumoasă de vară, Vasile, elev de clasa a 12-a care urmează să dea bacul, se pregătea la informatică. El se află la bunicii săi unde nu are internet, și toată ziua a rezolvat exerciții cu matrici. A decis să ia o pauză, și-a luat foaia pe care era desenată o matrice de dimensiuni $N \times M$ care conține valori întregi, și a plecat în curte să își găsească o activitate nouă.

Afară a găsit un mușuroi de furnici și a decis să facă un mic joculeț cu $F$ dintre ele. El va lua pe rând, câte o furnică, și o va plasa în colțul stânga jos al matricii, fie el considerat de coordonate $( 0, 0 )$ . Acesta analizează traseul fiecărei furnici și notează unele puncte prin care trece aceasta. Dacă o furnică trece prin căsuța unui element din matrice, atunci valoarea din căsuța respectivă se va adăuga la scorul furnicii.

Furnicile găsite de Vasile sunt inteligente, prin urmare ele au următoarele proprietăți:

Fiecare furnică se va îndrepta către punctul de coordonate $( M, N )$ ;
Furnicile merg într-o linie dreaptă între două puncte consecutive observate de către Vasile;
Coordonatele punctelor au valori reale cu exact două zecimale;
Nu vor să piardă timp, așa că ele nu se vor îndepărta niciodată de ținta lor (sunt pe grind). Altfel spus, pentru două puncte consecutive $P$ și $Q$ , $x_Q - x_P \ge 0$ și $y_Q - y_P \ge 0$ .

Atenție! Traseul furnicilor este descris în planul cartezian. Consultați desenul de la exemplu!

Vasile este intrigat de aceste comportamente și dorește să știe scorul pentru fiecare furnică.

Date de intrare

Pe prima linie se vor afla dimensiunile matricii, $N$ și $M$ . Pe următoarele $N$ linii se vor afla câte $M$ numere întregi $v_i$ , care reprezintă numerele care se află în matricea din joculețul lui Vasile. Pe următoarea linie se va afla $F$ , reprezentând numărul de furnici care participă în cursă. Următoarele $F$ linii vor conține perechi de coordonate $( x_i, y_i )$ , numere reale cu exact două zecimale, reprezentând punctele observate pentru furnica $i$ . Ultima coordonată pentru o furnică va fi $( M, N )$ .

Date de ieșire

Pe linia $i$ se va afișa scorul furnicii cu numărul $i$ .

Restricții și precizări

$1 \leq N, M \leq 500$ ;
$-5000 \leq v \leq 5000$ ;
$1 \leq F \leq 10^5$ ;
$0 \leq x_i \leq N$ ;
$0 \leq y_i \leq M$ ;
Vom nota cu $L_{i}$ lungimea traseului furnicii $i$
$1 \leq L_{i} \leq 5 000$ pentru $i$ de la $1$ la $F$
Suma $L_{i}$ pentru $i$ de la $1$ la $F \leq 10^6$
Pentru teste în valoare de $11$ puncte, pentru două puncte consecutive $P$ și $Q$ , $x_Q - x_P = 0$ sau $y_Q - y_P = 0$ și toate punctele au coordonate întregi;
Pentru teste in valoare de alte $30$ de puncte, $F \leq 100$ , $1 \leq N, M \leq 50$ ;
Pentru teste în valoare de alte $28$ de puncte, toate punctele au coordonate întregi;
Pentru teste în valoare de alte $42$ de puncte, nu există restricții suplimentare;
Dacă o furnică merge pe marginea unei căsuțe și nu intră în interiorul ei, atunci ea nu va primi scorul respectivei căsuțe.
Atenție! Matricea valorilor specifice căsuțelor se citește în ordine de sus în jos ( $y$ descrescător), de la stânga la dreapta ( $x$ crescător). Punctele intermediare sunt date după coordonatele lor carteziene ( $x$ , $y$ ).

Exemplul 1

stdin

5 5
2 8 4 8 -1
9 5 3 1 4
10 0 10 6 7
11 -1 7 10 9
5 0 20 -15 8
4
3.80 1.20 4.60 3.66 5.00 5.00
1.20 1.70 2.10 3.75 5.00 5.00
0.00 4.00 3.00 4.00 3.00 5.00 5.00 5.00 
3.00 3.00 5.00 5.00

stdout

Explicație

Prima furnică va trece prin următoarele căsuțe:

$\red{5 \rightarrow 0 \rightarrow 20 \rightarrow -15 \rightarrow 10 \rightarrow 9 \rightarrow 7 \rightarrow 4 \rightarrow -1}$
$\red{\text{Scor total} = 39}$

A doua furnică va trece prin următoarele căsuțe:

$\green{5 \rightarrow 11 \rightarrow -1 \rightarrow 0 \rightarrow 5 \rightarrow 3 \rightarrow 4 \rightarrow 8 \rightarrow -1}$
$\green{\text{Scor total} = 34}$

A treia furnică nu intră în nici o căsuță, ci merge doar pe marginea lor. Deci, are scorul $\purple{0}$ .
A patra furnică trece prin următoarele căsuțe:

$\blue{5 \rightarrow -1 \rightarrow 10 \rightarrow 1 \rightarrow -1}$
$\blue{\text{Scor total} = 14}$

Furnica cu scorul cel mai mare este prima, cu un scor în valoare de $\red{39}$ .

Exemplul 2