Într-o matrice pătratică, pentru fiecare poziție identificată prin linia i și coloana j, se adună toate elementele care se găsesc pe linia i sau pe coloana j sau pe diagonalele care trec prin a[i][j] și sunt paralele cu diagonala principală sau cu diagonala secundară, cu precizarea că în această sumă, elementul a[i][j] apare o singură dată.

Cerința

Să se determine suma maximă care se obține prin procedeul prezentat mai sus precum și poziția corespunzătoare (linia și coloana) sumei maxime. Dacă există mai multe poziţii pentru care se obţine suma maximă, se va alege prima dintre acestea, în ordinea parcurgerii matricei pe linii.

Date de intrare

Fișierul de intrare suma7.in conține pe prima linie un număr natural n. Pe fiecare din următoarele n linii se găsesc câte n numere întregi, separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire suma7.out va conține pe prima linie valoarea maximă a sumei obținute, iar pe a doua linie poziția (linia și coloana, separate printr-un spațiu) corespunzătoare elementului pentru care s-a obținut suma maximă.

Restricții și precizări

• 2 ≤ n ≤ 300
• Elementele matricei sunt numere întregi dintre -10000 și 10000.

Exemplu

suma7.in

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

suma7.out

18
1 3

#include <bits/stdc++.h>
using namespace std;
ifstream cin("suma7.in");
ofstream cout("suma7.out");
int a[301][301] , sumalin[301] , sumacol[301] , smax , lmax , colmax , sdp[301] , sndp[301] , sds[601];
int main()
{
    int i , j , n , d , s;
    cin >> n;
    for(i = 1 ; i <= n ;i++)
        for(j = 1 ; j <= n ;j++)
        {
            cin >> a[i][j];
            sumalin[i] += a[i][j];
            sumacol[j] += a[i][j];
            d = i - j;
            if(d >= 0) sdp[d] += a[i][j];
            else sndp[-d] += a[i][j];
            sds[i+j] += a[i][j];
        }
    for(i = 1 ; i <= n ;i++)
        for(j = 1 ; j <= n ;j++)
        {
            s = sumalin[i] + sumacol[j] + sds[i+j] - a[i][j] * 3;
            if(i - j >= 0) s += sdp[i-j];
            else s += sndp[j-i];
            if(s > smax) {smax = s ; lmax = i ; colmax = j;}
        }
    cout << smax << endl << lmax << " " << colmax;
    return 0;
}