Pie Treasures (treasures.X)
FR's cows have been busily baking pies that contain gold coins! Each
pie has some number N_i (1 <= N_i <= 25) of gold coins, and each pie
is neatly labeled on its crust with the number of gold coins inside.
The cows have placed the pies very precisely in an array of R rows
and C columns (1 <= R <= C <= 100) out in the pasture. You have
been placed in the pasture at the location (R=1,C=1) and have
gathered the gold coins in that pie. You must make your way to the
other side of the pasture, moving one _column_ closer to the end point
(which is location (R,C)) with each move you make. As you step to
the new column, you may stay on the same row or change your row by
no more than 1. That is, from (r,c) you can move to (r-1,c+1), (r,
c+1), or (r+1,c+1). Of course, you would not want to leave the
field and fail to get some gold coins, and you must end up at (R,C).
Given a map of the pasture, what is the greatest number of gold
coins you can gather?
By way of example, consider this field of gold-bearing cow pies:
start-> 6 5 3 7 9 2 7
2 4 3 5 6 8 6
4 9 9 9 1 5 8 <-end
Here's one path:
start-> 6 5 3 7 9 2 7
\
2 4 3 5 6 8 6
\ / \
4 9 9-9 1 5-8 <-end
The path above yields 6+4+9+9+6+5+8 = 47 gold coins. The path below
is even better and yields 50 coins, which is the best possible:
start-> 6 5 3 7 9 2 7
\
2 4 3 5 6-8 6
\ / \
4 9 9-9 1 5 8 <-end
PROBLEM FILE NAME: treasures.X
INPUT FORMAT:
* Line 1: Two space-separated integers: R and C
* Lines 2..R+1: Each line contains C space-separated small integers in
the obvious order
SAMPLE INPUT:
3 7
6 5 3 7 9 2 7
2 4 3 5 6 8 6
4 9 9 9 1 5 8
OUTPUT FORMAT:
* Line 1: An integer (which fits easily into 32 bits) that is the
maximum number of gold coins that can be gathered
SAMPLE OUTPUT (details appear above):
50