You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

种花还是种草

题目描述

WFYZ校园里，有$N$个宿舍楼，宿舍楼 $i$ 到 宿舍楼 $j$ 的距离为 $d_{i,j}$。学校做连接宿舍楼道路的绿化，有些道路两侧种草，有些道路两侧种花。学校经费有限，一栋楼最多修建两条连接到其他楼的绿化道路，使得所有的楼座连通，而且连接一栋楼的两条路不能同时种花。你现在负责绿化道路的设计，又喜欢种花，请问在满足要求的情况下，种花路径的总长度的最大是多少？

输入格式

第一行一个整数 $N$;

接下来 $N$ 行，每行 $N-i$个数，第 $j$ 个数表示楼座 $i$ 到 $j$ 的距离 $d_{i,i+j}$。

输出格式

一个整数，表示种花道路的最大长度。

样例 #1

样例输入 #1

4
1 5 4
7 8
8

样例输出 #1

13

样例 #2

样例输入 #2

3
1 2
4

样例输出 #2

4

样例 #3

样例输入 #3

16
5 16 5 2 11 7 9 7 2 5 5 12 4 7 6
8 7 17 9 8 1 9 6 10 8 8 6 10 3
10 5 8 11 10 7 8 4 8 6 5 1 10
7 4 11 4 5 4 5 10 1 5 1 2
2 9 9 7 6 12 2 8 3 5 2
9 10 3 1 1 2 10 7 7 5
10 6 1 8 9 3 2 4 2
10 10 8 9 2 10 7 9
5 8 8 7 5 8 2
4 2 2 6 8 3
2 7 3 10 3
5 7 10 3
8 5 7
9 1
4

样例输出 #3

87

提示

• 样例#1解释 种花的道路为$1-3,2-4$,种草的道路为 $3-2$ ,种花的距离为 $5+8=13$.
• 数据范围

对于$15\%$的数据范围 $2\leq N\leq 4$ ;

对于$100\%$的数据范围 $2\leq N\leq 16$ ,$1\leq d_{i,j} \leq 10^9$.