Un proprietar vinde un teren de formă dreptunghiulară împărţit în M x N 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ţă
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:
1. 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.
2. 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 1 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 2 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
• 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.
