Bartolomeu has finally joined the Straw Hat's pirate fleet.
He is known for having powers that allow him to create impenetrable barriers of all shapes and sizes
, however, the last battles have left him with strange after effects.
He now can only use his powers once per day, and he can only create barriers in rectangular shapes.
But the greatest problem he has is that he is now allergic to all fish-mans(half fish, half men creatures), which inflict damage on him on contact.
Unfortunately, Bartolomeu got kidnapped by the evil fish-man pirate captain John Haddock and is forced to fight in square shaped arena full of fish-men and monsters.
Each square unit of the area is either empty, or is filled with combination of beasts and fishmen.
Fortunately, Bartolomeu has a radar which tells him how much damage can each unit square inflict on him, or how much damage, he can inflict on them.
It is known that the squares that Bartolomeu damages, appear with positive integers, while the squares that damage Bartolomeu, appear with negative value.
Since Bartolomeu is not good at maths, he wants you to create a program that tells him the maximum gross damage he can inflict.
The gross damage is the total of positive and negative integers in the area that he chooses to cover
If the gross reaches less than -9999, Bartolomeu dies.
Input Specifications:
You will be first given an integer n: 2<= n <= 100, which represt the dimensions of the area.
Then you will be given n^2 integers d separated by white spaces: -9999 <= d <= +9999, which represent the damage on each unit square of the area
Output Specificartions:
You have to show one integer(possibly long long, or long for Java Users),which represents the maximum gross damage that Bartolomeu can inflict!
If the gross damage is less than -9999, output "Fatality!" instead, without double quatations.
Sample input:
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
Sample output:
15