DFS Order

문제

Bessie has a simple undirected graph with vertices labeled $1\dots N1\backslash dots\; N$ ($2\le N\le 7502\backslash le\; N\backslash le\; 750$). She generates a depth-first search (DFS) order of the graph by calling the function dfs($11$), defined by the following C++ code. Each adjacency list (adj[$ii$] for all $1\le i\le N1\backslash le\; i\backslash le\; N$) may be permuted arbitrarily before starting the depth first search, so a graph can have multiple possible DFS orders.

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);
}

You are given the initial state of the graph as well as the cost to change the state of each edge. Specifically, for every pair of vertices $(i,j)(i,j)$ satisfying , you are given an integer $a_{i,j}a\_\{i,j\}$ () such that

• If $a_{i,j}>0a\_\{i,j\}>0$, edge $(i,j)(i,j)$ is not currently in the graph, and can be added for cost $a_{i,j}a\_\{i,j\}$.
• If , edge $(i,j)(i,j)$ is currently in the graph, and can be removed for cost $-a_{i,j}-a\_\{i,j\}$.

Determine the minimum total cost to change the graph so that $[1,2\dots ,N][1,2\backslash dots,N]$ is a possible DFS ordering.

입력

The first line contains $NN$.

Then $N-1N-1$ lines follow. The $j-1j-1$th line contains $a_{1,j},a_{2,j},\dots ,a_{j-1,j}a\_\{1,j\},\; a\_\{2,j\},\; \backslash dots,\; a\_\{j-1,j\}$ separated by spaces.

출력

The minimum cost to change the graph so that $[1,2,\dots ,N][1,2,\backslash dots,\; N]$ is a possible DFS ordering.

4
1
2 3
40 6 11

10

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

5

4
-1
-2 300
4 -5 6

9