图 1 展示了一个数字蜂窝（蜂窝的边长为 3）。一条路径从最上面一行的某个节点开始，到最下面一行的某个节点结束。从一个节点出发，路径只能向左下方或右下方移动。在创建穿过蜂窝的路径时，你最多可以在蜂窝的某一行上交换两个数字一次。（交换本质上意味着在选定的一行中，你可以将该行中最大的数字放置到该行的任意位置。）你的任务是编写一个程序，计算在使用在选定行上交换两个数字的能力后，路径上数字之和的最大值。

图 1. 边长为 3 的蜂窝。

数据范围

• 节点中的数字是 $0$ 到 $99$ 之间的整数。
• 蜂窝的边长是 $1$ 到 $99$ 之间的整数。

输入格式

蜂窝的边长位于第一行。如果边长为 $n$，则蜂窝由 $2n - 1$ 行组成。蜂窝各行的数字位于接下来的 $2n - 1$ 行中。

输出格式

输出路径上数字之和的最大值。

样例

输入格式 1

3
1 2 3
3 2 2 1
4 2 8 0 3
5 3 1 2
3 1 4

输出格式 1

22

说明

在图 1 中，正确的解（$3 + 2 + 8 + 5 + 4 = 22$）被标为灰色。注意，第 4 行（从上往下数）上的数字 '5' 被交换到了该行的第 3 个位置（从左往右数）。