Un proprietar vinde un teren de formă dreptunghiulară împărțit în MxN parcele de formă pătrată cu lungimea laturii de o unitate. Fiecare parcelă costă V lei. Vlad s-a interesat și a aflat pentru fiecare din parcelele terenului care este valoarea de revânzare. El constată că unele parcele i-ar putea aduce profit, iar altele i-ar aduce pierdere. Fiind isteț, negociază cu proprietarul să cumpere atâtea parcele de teren câte pot fi împrejmuite cu un singur gard de lungime egală cu 2M+2N unități. Terenul are pe fiecare din cele patru laturi acces la drumul exterior, pe o porțiune de lungime egală cu o unitate. Vlad negociază astfel încât terenul achiziționat să conțină și cele patru parcele de acces la exterior.

Cerința

Cunoscând M și N – dimensiunile terenului, V – prețul de cumpărare al fiecărei parcele, x_nord, x_sud, y_vest și y_est – pozițiile parcelelor cu acces la drumul exterior și A[i][j], 1≤i≤M și 1≤j≤N – valorile de revânzare pentru fiecare parcelă, să se determine:

a) Profitul P_arie_minimă pe care-l poate obține Vlad după cumpărarea și apoi revânzarea suprafeței de teren de arie minimă, împrejmuită conform condițiilor negociate.
b) Profitul maxim P_max pe care-l poate obține Vlad după cumpărarea și apoi revânzarea unei suprafețe de teren împrejmuită conform condițiilor negociate.

Date de intrare

Fișierul fence.in conține pe prima linie numărul t.
Pentru toate testele de intrare numărul t poate avea doar valoarea 1 sau valoarea 2.
Pe linia a doua se găsesc numerele M, N, V, x_nord, x_sud, y_vest și y_est separate prin câte un spațiu, iar pe următoarele M linii se află câte N numere naturale separate prin câte un spațiu, reprezentând valorile de revânzare ale celor MxN parcele de teren.

Date de ieșire

Dacă valoarea lui t este 1, atunci se va rezolva numai punctul a) din cerință.
În acest caz în fișierul de ieșire fence.out se va scrie pe prima linie numărul P_arie_minimă.
Dacă valoarea lui t este 2, atunci se va rezolva numai punctul b) din cerință.
În acest caz în fișierul de ieșire fence.out se va scrie pe prima linie numărul P_max.

Restricții și precizări

• 3 ≤ M ≤ 1 000
• 3 ≤ N ≤ 1 000
• 1 000 ≤ V ≤ 10 000
• 2 ≤ x_nord ≤ N-1, 2 ≤ x_sud ≤ N-1, 2 ≤ y_vest ≤ M-1, 2 ≤ y_est ≤ M-1
• (x_nord-x_sud)∙(y_est-y_vest) ≥ 0
• 1 ≤ A[i][j] ≤ 20 000
• Prin profit se înțelege suma valorilor de revânzare corespunzătoare parcelelor din suprafața împrejmuită din care se scade produsul dintre prețul de cumpărare V și numărul parcelelor împrejmuite, care poate fi și negativ.
• Pentru rezolvarea corectă a primei cerințe se va obține 20% din punctaj.
• Pentru 33% din testele corespunzătoare cerinței b) va fi îndeplinită condiția M ≤ 15 și N ≤ 15.

Exemplul 1

fence.in

1
5 7 6 3 5 3 2
3 5 8 4 9 8 7
9 3 7 6 4 5 9
6 6 8 2 5 4 8
3 3 4 7 7 2 1
8 7 9 2 8 4 2

fence.out

3

Explicație

M=5, N=7, V=6, x_nord=3, x_sud=5, y_vest=3, y_est=2.

P_arie_minimă = (8+7+6+4+5+9+6+6+8+2+5+7+8)-6∙13 = 81-78 = 3

Exemplul 1

fence.in

2
5 7 6 3 5 3 2
3 5 8 4 9 8 7
9 3 7 6 4 5 9
6 6 8 2 5 4 8
3 3 4 7 7 2 1
8 7 9 2 8 4 2

fence.out

8

Explicație

M=5, N=7, V=6, x_nord=3, x_sud=5, y_vest=3, y_est=2

P_max = ( 8+4+9+8+7+7+6+4+5+9+6+6+8+2+5+7+7+8)-6∙18 = 116 - 108 = 8