ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Open Ural FU Championship 2011

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. New Year Cruise

Time limit: 1.0 second
Memory limit: 64 MB
And I drank it straight down.
In the life of Russian people there is always a place for a holiday! Even more so when several causes for celebration follow each other — New Year, Orthodox Christmas, Old New Year… People celebrate these holidays in different ways. Some of them like to be together with their family and friends, while others prefer to go for a travel. The company “Siberian Railroads” decided to combine these two variants by introducing a special cruise train “Booze” traveling along the route Vladivostok–Moscow–Vladivostok. The train would cruise once in a year only, during the New Year holidays. It would be adapted for celebrating each of the holidays up until the following holiday or until arriving to the destination.
When the company started selling tickets for the train, they turned out to be in great demand. The sale was stopped on the third day because a train for all those wishing to go on the cruise would be too long to fit any station. The company's managers calculated the number of tickets sold for the travel between each pair of stations, and they wanted to know the number of cars in the train sufficient to accommodate all the passengers.

Input

The first line contains the number n of stations where the train stops when traveling in one direction (2 ≤ n ≤ 100). The stations are numbered from 1 to n in the order the train passes them. Vladivostok is numbered 1 and Moscow is numbered n. In the following n lines you are given an n × n matrix with integer elements aij. The element aij is the number of people who have bought a ticket from station i to station j (0 ≤ aij ≤ 1 000; aii = 0); these people will board the train traveling from Vladivostok to Moscow if i < j and the train traveling in the opposite direction if i > j.

Output

Output the minimal number of cars in the train that is sufficient to accommodate all the passengers. There are exactly 36 seats in each car.

Sample

inputoutput
3
0 180 180
0 0 180
360 0 0
10
Problem Author: Denis Dublennykh
Problem Source: Open Ural FU Championship 2011
To submit the solution for this problem go to the Problem set: 1869. New Year Cruise