OLIMPIADA DE INFORMATICA

Etapa municipala IASI, 20 ianuarie 2007

 Clasa a X a

Problema 1 - ture

100 puncte

Sa consideram o matrice cu N linii si N coloane cu elemente numere naturale. In aceasta matrice trebuie sa plasam doua ture, īn pozitii distincte. Spunem ca un element al matricei este atacat daca se afla pe aceeasi linie sau pe aceeasi coloana cu una dintre cele doua ture. Elementele din pozitiile celor doua ture nu sunt considerate atacate. Turele vor fi plasate astfel incat suma elementelor atacate sa fie cat mai mare.

Cerinta
Scrieti un program care sa determine suma elementelor atacate (maxima posibil).

Date de intrare
Fisierul de intrare ture.in va contine pe prima linie un numar natural N, cu semnificažia din enunt. Pe fiecare dintre urmatoarele N linii se afla cate N numere naturale, reprezentand elementele matricei.

Date de iesire
Fisierul de iesire ture.out va contine o singura linie pe care va fi scrisa suma maxima.

Restrictii
2 <= N <= 100
Elementele matricei sunt numere naturale < 255.

Exemplu

ture.in ture.out Explicatie
5
4 2 2 3 3
4 2 1 4 0
1 3 4 0 1
4 3 0 2 3
0 0 3 0 4		 40

Prima tura va fi plasata īn pozitia (4,3), iar cea de a doua tura va fi plasata īn pozitia (2,5)
Elementele atacate sunt:
4,3,T,2,3 de pe linia 4 (T pozitia turei)
2,1,4,T,3 de pe coloana 3
4,2,1,4,T de pe linia 2
3,T,1,3,4 de pe coloana 5

Timp maxim de executie/test: 1 secunda