Pebbles

You have an unlimited supply of pebbles to place on an $N \times N$ board, where $3 \le N \le 15$. Every square holds a positive point value between $10$ and $99$ inclusive. For example, a $6 \times 6$ board might look like this:

Place pebbles on the board subject to two rules:

• At most one pebble may sit on any single square.
• No two pebbles may occupy adjacent squares. Two squares are adjacent when they touch horizontally, vertically, or diagonally.

The board never wraps around, so squares at opposite ends of a row or column, and the two far corners, are not adjacent.

Your score is the sum of the point values of every square that holds a pebble. Maximize this score.

The input may contain several boards; report the best attainable score for each one.

Each board is a block of $N$ lines, and every line lists $N$ space-separated point values (one per square). A blank line separates consecutive boards. Keep reading boards until the input ends.

For each board, print a single integer on its own line: the maximum total score achievable by a valid pebble placement.