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

vector<bool> vis(N + 1);
vector<vector<int>> adj(N + 1);  // adjacency list
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

4
1
2 3
40 6 11

样例输出 1

10

样例输入 2

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

样例输出 2

5

样例输入 3

4
-1
-2 300
4 -5 6

样例输出 3

9

说明

初始时，图包含边 $(1,2),(1,3),(2,4)$。移除边 $(2,4)$ 并添加边 $(1,4)$ 的总代价为 $5+4=9$。

数据范围

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