题目描述

德黑兰的$TTT$出租车服务公司需要将一些杂志送到德黑兰的$N$个地点，这些地点标号为$L_1$到$L_N$。$TTT$公司为此安排了$3$辆汽车。在时间$0$时，所有$3$辆汽车和杂志都位于$L_1$。$L_1$有充足的杂志供应，汽车可以携带任意数量的杂志。杂志必须按照以下规则送达所有地点：

对于所有$i = 2 \dots N$，杂志必须在$L_{i-1}$送达之后才能送达$L_i$。 任何时候，$3$辆汽车中只能有一辆在行驶，另外两辆必须停在其他地点休息。

任意汽车从$L_i$到$L_j$（或反向）的行驶时间为正整数，记为$D[i,j]$。

我们的目标是为汽车制定一个配送计划，使得所有$N$个地点的杂志都送达的时间最短。

请编写程序计算这个最短配送时间。

输入

输入文件包含$M$个问题实例（$1 \leq M \leq 10$）。输入的第一行是$M$，随后是各个输入数据的描述。每个实例以单独一行的$N$开头（$N \leq 30$）。接下来的$N-1$行中，第$i$行包含$D[i,j]$的值（所有$i=1 \dots N-1$，$j=i+1 \dots N$）。

输出

输出包含$M$行，每行对应一个输入数据的解。每行输出送达所有$N$个地点所需的最短时间。

输入数据 1

1
5
10 20 3 4
5 10 20
8 18
19

输出数据 1

22

来源

德黑兰1999竞赛