题目描述

Bessie 有一个无向简单图，结点编号为 $1\dots N$（$2\le N\le 750$）。她通过调用函数 $\texttt{dfs}(1)$ 生成该图的一个深度优先搜索（depth-first search，DFS）序，函数由以下 C++ 代码定义。各邻接表（对于所有 $1\le i\le N$ 的 $\texttt{adj}[i]$）在开始深度优先搜索之前可以任意排列，因此一个图可以有多个可能的 DFS 序。

vector<bool> vis(N + 1);
vector<vector<int>> adj(N + 1);  // 邻接表
vector<int> dfs_order;

void dfs(int x) {
    if (vis[x]) return;
    vis[x] = true;
    dfs_order.push_back(x);
    for (int y : adj[x]) dfs(y);
}

给定图的初始状态以及修改每条边状态的代价。具体地说，对于每对满足 $1\le i<j\le N$ 的结点 $(i,j)$，给定一个整数 $a_{i,j}$（$0<|a_{i,j}|\le 1000$），其中

• 如果 $a_{i,j}>0$，则边 $(i,j)$ 当前不在图中，可以以代价 $a_{i,j}$ 添加。
• 如果 $a_{i,j}<0$，则边 $(i,j)$ 当前在图中，可以以代价 $-a_{i,j}$ 移除。

求使得 $[1,2\dots,N]$ 成为一个可能的 DFS 序的最小总代价。

输入格式

输入的第一行包含 $N$。

以下 $N-1$ 行，第 $j-1$ 行包含 $a_{1,j}, a_{2,j}, \dots, a_{j-1,j}$，以空格分隔。

输出格式

输出使得 $[1,2,\dots, N]$ 成为一个可能的 DFS 序的最小总代价。

输入输出样例 #1

输入 #1

4
1
2 3
40 6 11

输出 #1

10

输入输出样例 #2

输入 #2

5
-1
10 -2
10 -7 10
-6 -4 -5 10

输出 #2

5

输入输出样例 #3

输入 #3

4
-1
-2 300
4 -5 6

输出 #3

9

说明/提示

样例 1 解释：

初始时，图中没有边。可以添加边 $(1,2),(2,3),(2,4)$ 可以得到总代价 $1+3+6$。现在图有两个可能的 DFS 序：$[1,2,3,4],[1,2,4,3]$。

样例 2 解释：

初始时，图中包含边 $(1,2),(2,3),(2,4),(1,5),(2,5),(3,5)$。移除边 $(3,5)$ 可以得到总代价 $5$。

样例 3 解释：

初始时，图中包含边 $(1,2),(1,3),(2,4)$。移除边 $(2,4)$ 并且添加边 $(1,4)$ 可以得到总代价 $5+4=9$。

• 测试点 $4\sim 9$：所有 $a_{i,j}>0$。
• 测试点 $10\sim 16$：$N\le 50$。
• 测试点 $17\sim 23$：没有额外限制。