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.