ashu-and-hog-riders

There is war and ashu needs hog riders for the fight. The area on which hog riders live is a N X N square matrix. If A[i][j] = 1 it means a hog rider is standing at that place and if it is 0 then the place is empty. To call them ashu stands on any tile on which a hog is present  and makes that particular hog shout loud. All the hog riders standing adjacent to the tile where one shouts listen and they also start shouting so again those hogs which are connected to them also starts shouting and calling others for war. So you have to output the best position where ashu should go so that maximum hog riders will attend the war. 
Adjacent to a tile means tiles which lie on above,below,left and right of that tile. Ashu can't stand on a tile which is empty or else he has to make the noise which is not  possible 
Input
First line contains N as input which is size of matrix. Next N lines contain N integers as 0 or 1 indicating gaps and hogs
Output
You have to output the maximum number of hogs that can be called
Scoring
1≤ N ≤ 10      20pts
1≤ N ≤ 100    40pts
1≤ N ≤ 1000  40pts

SAMPLE INPUT
3
1 1 1
1 0 0
0 1 1

SAMPLE OUTPUT
4

Explanation

If ashu stands at any of the first four cells then 4 hogs will come for war

Source: hackerearth | Difficulty: EASY


Solutions: