Description

一个$n×n$的格子棋盘，在每个格子里面都有一个非负数，从中取出若干数，所取的数不可以相邻并且取出的数之和最大。

Format

Input

包含多个测试实例，每个测试实例都包含一个整数$n$ 和$n×n$个非负数$（n ≤20）$。

Output

对每个测试实例都单行输出可能取得的最大和值。

Samples

3
75 15 21
75 15 28
34 70 5

188