2007/2008 SOUTHERN CALIFORNIA REGIONAL
ACM INTERNATIONAL COLLEGIATE PROGRAMMING CONTEST

Problem 6
Pebbles

You are given an unlimited number of pebbles to distribute across an N × N game board (1 <= N <= 15), where each square on the board contains an integer point value between 1 and 99, inclusive. The integers on a given board may not be unique. A 6 × 6 board might look like this:
78   78   11   55   20   11
98   54   81   43   39   97
12   15   79   99   58   10
13   79   83   65   34   17
85   59   61   12   58   97
40   63   97   85   66   90
The player distributes pebbles across the board so that:
At most one pebble resides in any given square.
No two pebbles are placed on adjacent squares. Two squares are considered adjacent if they are horizontal, vertical, or diagonal neighbors. There is no board wrap-in the above example, 55 and 85 are not neighbors, nor are 13 and 17.
The goal is to maximize the number of points claimed by your placement of pebbles.
Input to your program will be a sequence of boards, terminated by end-of-file. Each board will be separated from the next by a blank line. Each board is a sequence of N lines consisting of N integers separated from each other by whitespace.
For each board, your program is to print a line containing the maximum number of points attainable. The result is to begin in the first column with no leading zeroes or trailing whitespace.

Sample Input

 71 24 95 56 54
 85 50 74 94 28
 92 96 23 71 10
 23 61 31 30 46
 64 33 32 95 89
 
 78 78 11 55 20 11
 98 54 81 43 39 97
 12 15 79 99 58 10
 13 79 83 65 34 17
 85 59 61 12 58 97
 40 63 97 85 66 90
 


Output for the Sample Input

 572
 683



File translated from TEX by TTH, version 3.77.
On 18 Nov 2007, 08:00.