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.

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 a_ij. The element a_ij is the number of people who have bought a ticket from station i to station j (0 ≤ a_ij ≤ 1 000; a_ii = 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 the minimal number of cars in the train that is sufficient to accommodate all the passengers. There are exactly 36 seats in each car.