You're given an unlimited number of pebbles to distribute across an n x n game board (n drawn from [3, 15]), where each square on the board contains some positive point value between 10 and 99, inclusive. A 6 x 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.

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

Input

Each board is expressed as a series of lines, where each line is a space-delimited series of numbers. A blank line marks the end of each board (including the last one).

Output

Print the maximum number of points one can get by optimally distributing pebbles while respecting the two rules. Each output should be printed on a single line.