\includegraphics{https://static.e-olymp.com/content/aa/aab5f4edb53507cb97ae40eca27fa49d7efe4190.jpg} Misha, like his cartoon friend of Winnie the Pooh, was very fond of honey. So he waited impatiently for the moment when the apiary could be tackled his collection. However, there are several problems, primarily due to the fact that the bees themselves is not very fond of this day, when the bear was collecting honey ... To bee able to continue to bring honey and suffered as little as possible, so that he himself was bitten by the same bees smaller (ie, the bear has not been twice on one and the apiary site, where the beehives from which honey is withdrawn ), Misha during collection always began gathering honey in the upper left corner of his apiaries and continue to move only right and down until it reaches the bottom right hive, and then moved back to the beginning, but moved to an apiary only the left and up. Help Misha find a route on which he will gather the largest number of his favorite treats. \InputFile The input data contain several test cases. Each test case begins with the line, which indicates the number of hives in the apiary \textbf{N} (\textbf{1} < \textbf{N} ≤ \textbf{600}). Subsequent \textbf{N} lines each test set the weight in kilograms of honey, which bear may be taken from a given point situated in the apiary hive. It is known that bees in each hive could not collect more than \textbf{100} kilograms of honey. \OutputFile For each test case the optimal output in terms of Misha's crop of honey.