cetate

Cetatea Vizima din regatul Temeria poate fi reprezentată printr-o matrice cu $N$ linii și $M$ coloane, numerotate începând cu $1$. Vizima este o cetate înfloritoare, fapt datorat numărului mare de negustori și meșteri prezenți. Din acest motiv, fiecărei celule îi este atribuit un profit corespunzător zonei respective. Regele Foltest dorește să reconstruiască zidurile cetății, dar cum războiul cu Imperiul Nilfgaard bate la ușă și resursele regatului sunt limitate, el trebuie să aleagă o porțiune pe care să o poată apăra, reprezentată ca o submatrice. O submatrice este identificată printr-o configurație de patru numere $(i_1, j_1, i_2, j_2)$ ($1 \leq i_1 \leq i_2 \leq N$, $1 \leq j_1 \leq j_2 \leq M$), în această ordine, și este formată din elementele situate pe liniile consecutive $i_1, i_1+1, \ldots, i_2$ și pe coloanele consecutive $j_1, j_1+1, \ldots, j_2$ ale matricei prin care este reprezentată cetatea. Laturile submatricei sunt egale cu numărul de linii, respectiv de coloane din care a preluat elemente, iar profitul submatricei este suma valorilor din celulele sale.

Cerințe

Scrieți un program care, cunoscând matricea cetății și o valoare $K$, determină:

1. profitul maxim al unei submatrice cu laturile egale cu $K$, precum și configurația prin care se identifică ea.
2. profitul maxim al unei submatrice cu laturile cel mult egale cu $K$, precum și configurația prin care se identifică ea.

Date de intrare

Fișierul de intrare cetate.in conține pe primul rând o valoare $c$ egală cu $1$ sau $2$, reprezentând cerința ce urmează a fi rezolvată. Următoarea linie conține în ordine $N$, $M$ și $K$, cu semnificația din enunț, iar pe următoarele $N$ linii se află câte $M$ numere, reprezentând valorile din matricea dată. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire cetate.out va conține pe prima linie profitul maxim cerut, conform cerinței, iar pe a doua linie va conține 4 numere naturale, reprezentând configurația prin care se identifică submatricea obținută. Dacă există mai multe submatrice conform cerinței, se va lua în considerare cea pentru care configurația formată din cele 4 numere de mai sus este minim lexicografică.

Restricții și precizări

• $1 \leq N,M \leq 400$
• $1 \leq K \leq min(N,M)$
• Valorile date pentru matricea cetății se află în intervalul $[-10^9, 10^9]$.
• Pentru teste în valoare de 20 de puncte, $c=1$, iar pentru restul testelor, în valoare de 70 de puncte, $c=2$. Pentru teste în valoare de 8 puncte, $c=1$ și $1 \leq N,M \leq 70$. Pentru teste în valoare de 25 de puncte, $c=2$ și $1 \leq N,M \leq 70$.
• Configurația $(x_1, x_2, x_3, x_4)$ este mai mică din punct de vedere lexicografic decât configurația $(y_1, y_2, y_3, y_4)$ dacă există $p$ astfel încât $x_p < y_p$ și $x_1 = y_1$, $x_2 = y_2$, $\dots$, $x_{p-1} = y_{p-1}$.

Exemplul 1

cetate.in

1
3 4 3
-1 -1 -1 -1
-1 2 -1 -1
-1 -1 -1 -1

cetate.out

-6
1 1 3 3

Explicație

În acest exemplu, se rezolvă cerința 1. S-a determinat submatricea cu configurația $(i_1=1, j_1=1, i_2=3, j_2=3)$, formată din elementele aflate pe liniile 1, 2 și 3 și coloanele 1, 2 și 3. O altă submatrice cu profitul $-6$ este cea dată de configurația $(1,2,3,4)$, care însă este mai mare din punct de vedere lexicografic decât cea afișată, de aceea nu este o soluție acceptată.

Exemplul 2

cetate.in

2
3 4 3
-1 -1 -1 -1
-1 2 1 -1
-1 -1 -1 -1

cetate.out

3
2 2 2 3

Explicație

În acest exemplu, se rezolvă cerința 2. Au fost considerate toate submatricele cu laturile $1$, $2$ sau $3$, iar submatricea găsită, cu laturile $1$ și $2$, este singura submatrice de profit maxim care respectă condițiile impuse de cerință.