Finding maximum paths Given a square of positive, natural numbers write a program find a horizontal and a vertical path with the sum of numbers along them being maximal. A horizontal path goes from the first column to the last and has to increase its column position by one in each step. A vertical path goes from the first row to the last and has to increase its row position by one in each step. Furthermore the row position in a horizontal path may stay the same or change by one in either direction, likewise for vertical paths.

To illustrate, the following could be a valid path:



The following path would be invalid, since it steps backwards (and remains on the same row in some places):



The following path would be equally invalid, since it changes the row position by more than one in a single step:



Note: The solution should run in an acceptable amount of time.

Input

n lines of input with n space-separated positive integers each are given on standard input. 2 ≤ n ≤ 40. Every line is terminated by a line break. The numbers are small enough that the maximum sum fits in a 32-bit signed integer.

Output

The maximum sums of the horizontal and vertical paths (in that order) separated by a single space.

Sample input 1

1 2
1 2


Sample output 1

3 4


Sample input 2

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 4 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 4 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1


Sample output 2

37 35


Sample input 3

683 671 420 311 800 936
815 816 123 142 19 831
715 588 622 491 95 166
885 126 262 900 393 898
701 618 956 865 199 537
226 116 313 822 661 214


Sample output 3

4650 4799




For your convenience we have prepared a few test cases in bash (thanks to Ventero) and PowerShell which you can run your program through. Invocation is: &lt;test&gt; &lt;command line&gt;, so something like ./test python paths.py or ./test.ps1 paths.exe. Have fun :-)
GolfScript - 49 Nabb enhanced characters
51 characters
50 strictly and utterly necessary characters + 3 slackers that only did the job of 1
56 mostly redundant characters
n%{~]}%.zip{{0@+\{\.1&gt;\3&lt;$-1=@+}%\;}*$-1=\}2*' '@

51 solution:
n%{~]}%.zip{(\{0@+\{\.1&gt;\3&lt;$-1=@+}%\}%;$-1=\}2*' '@

53 solution:
n/{~]}%);.zip{(\{0@+\{\.1&gt;\3&lt;$-1=@+}%\}%;$-1=\}2*' '@
             a8_b9___c10___11______12 13      14_

The method works on two lines at a time, one containing the maximum sums reached at each point, and one containing the next line.
a/14: Repeat twice, once for each result.
8: Take the first line from the input and switch it behind the input array, this in now the first set of maximum sums.
b/13: Iterate over each remaining line in the array.
9: Put 0 at the beginning of the maximum sums.
c/12: Iterate over each element of the line.
10: Make a copy of the maximum sums with the first element removed.
11: Take the first 3 elements of the maximum sums, sort them and add the largest to the current element of the line.
56 solution:
n/{~]}%);.zip{1,99*\{{\.1&gt;\3&lt;$-1=@+}%0\+\}%;$-1=\}2*' '@
1________2___ 3____ 4______________________5_____ 6_7___

1: From input to array of arrays in 9 characters, actually it could have been done with just 1, but I broke that key so this will have to do.
2: 4 characters just to make a transposed copy.
3: Array of 99 0s in 5 characters, it could probably be done in a way smarter fashion, but I smoke too much weed to figure how.
4: Overly complicated double loop that iterate over every single element of the input and does some fuzzy logic or something like that to produce the result. Nabb will probably make something equivalent in around 3½ characters.
5: By now the result is there, inside an array that is, this silly piece of code is just there to get it out (and junk a piece of leftovers (and switch the result into place)).
6: This is a command so simple that its character count would probably be negative in an optimal solution.
7: At this point the program is really done, but due to sloppiness in the preceding code the output is in the wrong order and lacks a space, so here goes a few more bits down the drain.