DFS 순서

벤시는 정점에 $1$부터 $N$까지 번호가 붙은 단순 무방향 그래프를 가지고 있다 ($2 \le N \le 750$). 벤시는 아래 코드의 dfs(1)을 호출해 그래프의 DFS 순서를 만든다. 각 인접 리스트 adj[i] ($1 \le i \le N$)는 탐색을 시작하기 전에 임의로 순서를 바꿀 수 있으므로, 같은 그래프라도 가능한 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 순서가 되도록 그래프를 바꾸는 데 드는 최소 비용을 출력한다.