题目描述

如下图，是一个边长为 $3$ 的蜂窝图，每个点有点权：

现在要从上面一行的某一点到最下面的一行某一点，每次只可以到达左下角的点和右下角的点，您最多可以交换选定的一行中的两个点的数值。

求通过交换，从上面一行的某一点到最下面的一行某一点的点权之和的最大值是多少。

输入格式

第一行一个整数 $n$ 代表蜂窝图的边长。
接下来 $2n-1$ 行每行若干个整数代表一个蜂窝图。

输出格式

一行一个整数代表答案。

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

22

提示

样例说明

对于样例 $1$，交换第四行的 $5$ 和 $1$，然后我们就可以得到一条点权之和最大的路径：

最大值为 $22$。

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 99$，$0 \le$ 蜂窝图中的每个图 $\le 99$。

说明

翻译自 BalticOI 2000 Day1 A Honeycomb Problem。