Problem M. 你说的对，但是这是最长路径

时间限制：3 second

空间限制：512 megabytes

Background

我们定义：若矩阵 $L$ 具有下列形式，则T称矩阵 $L$ 为下三角矩阵。

$$L = \left[ \begin{matrix} l_{1,1} &&&& 0 \\ l_{2,1} & l_{2,2} &&& \\ l_{3,1} & l_{3,2} &\ddots && \\ \vdots & \vdots &\ddots & \ddots & \\ l_{n,1} & l_{n,2} &\cdots & l_{n,n-1} & l_{n,n} \\ \end{matrix} \right] $$

我们可以发现，对于一个 $n$ 阶下三角矩阵中，共有 $n$ 行 $n$ 列数据，对于第 $i\ (1 \le i \le n)$ 行共有 $i$ 个 $(l_{i,1} \rightarrow l_{i,i})$ 有效数据，对于第 $i\ (1 \le i \le n)$ 列共有 $n - i + 1$ 个 $(l_{i,i} \rightarrow l_{n,i})$ 有效数据。

Description

对于一个 $n$ 阶的下三角矩阵，我们将它的每个有效数据看作是一个可以经过的结点。显然，这个下三角矩阵中将共有 $\frac{n(n+1)}{2}$ 个结点。

现在，我们更加直观地来看一下这个矩阵图。如果我们用 $l_{i, j}$ 表示第 $i$ 行第 $j$ 列的结点，对于所有的 $1 \le j \le i < n$，有：

• 一条权值为 $a_{i,j}$ 的边，连接结点 $l_{i, j}$ 和 $l_{i + 1, j}$ ；
• 一条权值为 $b_{i,j}$ 的边，连接结点 $l_{i, j}$ 和 $l_{i + 1, j + 1}$ ；
• 一条权值为 $c_{i,j}$ 的边，连接结点 $l_{i + 1, j}$ 和 $l_{i + 1, j + 1}$ ；

保证对于任意三个结点 $l_{i,j}, l_{i + 1,j}, l_{i + 1, j + 1}$ 之间连通的边权值满足三角形定理。

即满足 $a_{i,j} + b_{i,j} > c_{i,j},a_{i,j} + c_{i,j} > b_{i,j}, b_{i,j} + c_{i,j} > a_{i,j}$ 。

如果还是不能理解矩阵图的构造方式，下图可以形象地表示出这个构造方式。

对于每一条带权边，只能允许通过一次，并且通过这条边的花费即为边的权值。 $zms$ 想知道从结点 $l_{1,1}$ 到 $l_{n,n}$ 的一条路径，使得通过所有边的花费之和最大。这样的路径 $zms$ 认为是最长路径。

请你帮助 $zms$ 找到这样的最长路径，并求出最长路径的花费。

Input Format

对于每个测试点有多个测试用例。输入的第一行包含一个整数 $T$ ，表示测试用例的数量；

第二行包含一个整数 $n$ ，表示下三角矩阵的大小；

对于接下来 $n-1$ 行，第 $i$ 行输入 $i$ 个整数 $a_{i,1},a_{i,2},\cdots,a_{i,i}$ ，其中 $a_{i,j}$ 表示连接结点 $l_{i, j}$ 和 $l_{i + 1, j}$ 的边权值；

对于接下来 $n-1$ 行，第 $i$ 行输入 $i$ 个整数 $b_{i,1},b_{i,2},\cdots,b_{i,i}$ ，其中 $b_{i,j}$ 表示连接结点 $l_{i, j}$ 和 $l_{i + 1, j + 1}$ 的边权值；

对于接下来 $n-1$ 行，第 $i$ 行输入 $i$ 个整数 $c_{i,1},c_{i,2},\cdots,c_{i,i}$ ，其中 $c_{i,j}$ 表示连接结点 $l_{i + 1, j}$ 和 $l_{i + 1, j + 1}$ 的边权值；

Output Format

输出 $T$ 行，对于每个测试用例输出一行一个整数，表示最长路径的花费。

Sample Data #1

3
2
3
2
4
2
1
1
1
3
100
100 100
1
100 1
100
100 100

7
2
700

Data Range

$1 \le T \le 2.5 \times 10^3,\ 2 \le n \le 300,\ 1 \le a_{i,j}, b_{i,j}, c_{i,j} \le 10^9$ 。

输入保证对于所有测试用例满足 $\sum n \le 5 \times 10^3$ 。

保证对于任意三个结点 $l_{i,j}, l_{i + 1,j}, l_{i + 1, j + 1}$ 之间连通的边权值满足三角形定理。

即满足 $a_{i,j} + b_{i,j} > c_{i,j},a_{i,j} + c_{i,j} > b_{i,j}, b_{i,j} + c_{i,j} > a_{i,j}$ 。

Hint

样例的下三角矩阵的排列方式如下。