DWITE Online Computer Programming Contest, November 2002, Problem 4

A local radio station, COOL-FM (that's Cool with a "C"), recently awarded a lucky listener, the prize of walking through a giant sized chessboard with money prizes at each of the squares on the chessboard. The lucky listener, had to start at the lower left corner and move to the upper right corner, by taking steps either to the right or above (moving to the left, down or on a diagonal was not allowed). The lucky listener claimed each of the money prizes at each of the squares they stepped on.

Your job is to find the five best routes through the chessboard yielding the most money for the lucky listener.

Input Specification

The first line of the input will consist of an integer ~N \le 300~, the size of the chessboard. Each subsequent line represents one row on the chessboard. Each line will contain ~N~ integers for the locations on the chessboard for that row. Each integer ~A~ represents the amount of money at that location, ~0 \le A \le 1\,053~. These integers will be separated by a single space. The first number in the ~N^\text{th}~ line would be the starting point for the lucky listener. The ~N^\text{th}~ number in the first line would be the ending point.

Output Specification

The output will contain five lines of data, each representing the amount of money (as an integer) that would be obtained on the five best routes, from best to fifth best. It is possible to have different routes with the same amount.

Grading

The test data will have partial marks! One test case has ~N = 8~, but the other has ~N = 300~.

Sample Input

8
4 3 1 0 0 5 12 10
5 3 12 0 0 1 4 3
1 10 3 0 0 2 12 3
4 4 4 4 4 4 0 0
3 1 12 0 0 25 2 0
0 4 5 7 7 7 4 5
4 6 9 1 0 0 0 12
12 2 1 6 0 0 1 2

Sample Output

126
124
124
122
122