The 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 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 (i.e., 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

* 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

* Line 1: An integer (which fits easily into 32 bits) that is the maximum number of gold coins that can be gathered

USACO October, 2006 Qualification Round