D. Christmas Express

The Christmas Express is a train that transports passengers around the circular metro of the North Pole. This metro consists of $n$ stations, numbered consecutively from $1$ to $n$. The train stops at stations in the order $1,2,\dots ,n,1,2,\dots ,n,1,2,\dots$, continuing indefinitely.

Based on data from the past two years, Grandpa Frost has observed that each time the train stops at station $i$, a certain number of elves, $a_{i,j}$, board the train and travel to station $j$, for every $j$ where $j\ne i$. Grandpa Frost needs to determine the minimum number of seats required on the train to accommodate all passengers comfortably.

It is assumed that at each station, passengers disembark before new passengers board. Your task is to assist Grandpa Frost in finding the solution.

Input

The first line contains a single integer $n$ ($2\le n\le 500$), representing the number of stations.

Each of the following $n$ lines contains $n$ integers $a_{i,1},a_{i,2},\dots ,a_{i,n}$ ($0\le a_{i,j}\le 500$), where all $a_{i,i}$ are $0$.

Output

Output a single integer — the minimum number of seats required on the train.

Examples

Note

For example, if the train can only carry eight passengers at a time, it will not be sufficient for all elves. However, nine seats would be enough to accommodate them comfortably.