DWITE Online Computer Programming Contest
November 2002

Problem 4

Money Prize

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

The first line of the input will consist of an integer N ≤ 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 ≤ A ≤ 1053. These integers will be separated by a single space. The first number in the N^th line would be the starting point for the lucky listener. The N^th number in the first line would be the ending point.

Output

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.

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

All Submissions
Best Solutions

Point Value: 15
Time Limit: 1.00s
Memory Limit: 32M
Added: Mar 25, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

the problem only limits the size to a maximum of 300, how do we treat a size of less than 1? and for a size of 1 or 2, do we output 0 for the last 3 or 4 test cases? or just leave them empty? are any of these even tested? or should the problem include a lower limit of 3?

Assume N > 2.