Pebbles

Original source: ICPC Pacific Northwest 2007

Input and output formats changed

Time Limit: 1 second

You’re given an unlimited number of pebbles to distribute across an n-by-n game board (3 ≤ n ≤ 15), where each square on the board contains some two-digit point value. A 6-by-6 board might look like this:

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 even diagonal neighbours.
  • There’s no board wrap, so 44 and 61 of row three aren’t neighbours. Neither are 33 and 75 nor 55 and 92.

The goal is to maximise the number of points claimed by your placement of pebbles.

For example, it is valid (but not necessarily optimal) to place pebbles in the bolded squares below:

Write a program that reads a board from input and prints the maximum number of points attainable by an optimal pebble placement.

Input

The first line of input consists of an integer n (3 ≤ n ≤ 15), representing the dimension of the board. n lines follow, the ith of which consists of n space-separated integers, a_i, 1, a_i, 2, …, a_i, n (10 ≤ a_i, j ≤ 99), representing the point values of the squares comprising the ith row of the board.

Output

Output a single integer, the maximum number of points one can get by optimally distributing pebbles while respecting the two rules.

Sample Input 1

5
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

Sample Output 1

572

Sample Input 2

6
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

Sample Output 2

683

Explanation

In sample case 1, we should take:

• 71, 95 and 54 from the first row,
• 96 and 71 from the third row, and
• 64, 32 and 89 from the last row.