/*------------------------------------------------------------------------------
 * squirrel.c: Squirrel Hunt
**----------------------------------------------------------------------------*/

/* Copyright (c) 2009 Peter Bui. All Rights Reserved.
 *
 * Peter Bui <pbui@cse.nd.edu>
 *
 * Problem
 * -------
 *
 * This is the solution to problem 3 of the Fall 2009 NDACM Programming
 * contest, where given a grid of NxN squares where each square contains the
 * number of squirrels in that region, you must determine the total number of
 * squirrels in the path that allows you to hunt the most squirrels.  You must
 * move from the top left to the bottom right by either going down or right. 
 *
 * Solution
 * --------
 *
 * Use dynamic programming to generate a bottom up table of the maximum
 * squirrels killed in the optimal path from that square: each square in the
 * grid computes which neighboring square has the most squirrels to kill and
 * adds that to its population of squirrels.
 *
**------------------------------------------------------------------------------
 * Includes
**----------------------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*------------------------------------------------------------------------------
 * Constants 
**----------------------------------------------------------------------------*/

#define NMAX_SQUARES 100

/*------------------------------------------------------------------------------
 * Global Variables
**----------------------------------------------------------------------------*/

int G[NMAX_SQUARES + 1][NMAX_SQUARES + 1];  // Grid
int S[NMAX_SQUARES + 1][NMAX_SQUARES + 1];  // Squirrel Table

/*------------------------------------------------------------------------------
 * Functions
**----------------------------------------------------------------------------*/

static void 
read_grid(int n)
{
    int r, c;

    memset(G, 0, sizeof(int) * (NMAX_SQUARES + 1) * (NMAX_SQUARES + 1));

    for (r = 1; r <= n; r++) 
	for (c = 1; c <= n; c++)
	    scanf("%d", &(G[r][c]));
}

/*----------------------------------------------------------------------------*/

inline int
max(const int a, const int b)
{
    return ((a > b) ? a : b);
}

/*----------------------------------------------------------------------------*/
    
static void
compute_table(int n)
{
    int r, c;
    
    memset(S, 0, sizeof(int) * (NMAX_SQUARES + 1) * (NMAX_SQUARES + 1));

    for (r = 1; r <= n; r++)
	for (c = 1; c <= n; c++)
	    S[r][c] = max(S[r][c - 1], S[r - 1][c]) + G[r][c];
}

/*------------------------------------------------------------------------------
 * Main Execution
**----------------------------------------------------------------------------*/

int
main(int argc, char* argv[]) 
{
    int n;

    while (scanf("%d", &n) != EOF) {
	read_grid(n);
	compute_table(n);
	printf("%d\n", S[n][n]);
    }

    return (EXIT_SUCCESS);
}

/*------------------------------------------------------------------------------
 * vim: sts=4 sw=4 ts=8 ft=cpp
**----------------------------------------------------------------------------*/