Minimum Cost for DFS Order

Bessie has an undirected simple graph with vertices numbered from $1$ to $N$ ($2 \le N \le 750$). The graph is represented by its adjacency lists. Initially, for every pair of vertices $(i,j)$ with $1\le i<j\le N$, a cost $a_{i,j}$ is given (with $0<|a_{i,j}|\le 1000$), where:

• If $a_{i,j}>0$, then the edge $(i,j)$ is not present in the graph and can be added at a cost of $a_{i,j}$.
• If $a_{i,j}<0$, then the edge $(i,j)$ is present in the graph and can be removed at a cost of $-a_{i,j}$.

Bessie calls the following DFS routine starting from vertex $1$:

[ \begin{array}{l} vis[1 \dots N] = false,\ \text{dfs_order} = [,],\ \text{function } dfs(x): \ \quad \textbf{if } vis[x] \textbf{ then return}.\ \quad vis[x] = true,\ \quad dfs_order.push(x),\ \quad \textbf{for each } y \textbf{ in } adj[x] \textbf{ do } dfs(y).\ \end{array} ]

Before the DFS starts, Bessie can rearrange each adjacency list arbitrarily. Therefore, a single graph might yield multiple DFS orders.

The goal is to modify the graph with minimum total cost so that the sequence $[1,2,\dots,N]$ becomes a valid DFS order.

Observation: In order for $[1,2,\dots,N]$ to be a DFS order, there must be a DFS tree with the following chain of tree edges: $(1,2)$, $(2,3)$, ..., $(N-1,N)$. With the freedom to choose the order in each adjacency list, it is sufficient to ensure that for each $i$ from $1$ to $N-1$, the edge $(i,i+1)$ exists in the final graph. Any extra edge can be placed later in the adjacency order without affecting the DFS order.

Thus, for every $i=1,2,\dots, N-1$, if the edge $(i,i+1)$ is absent initially (i.e. $a_{i,i+1}>0$), you must add it at a cost of $a_{i,i+1}$. If $a_{i,i+1}<0$, the edge is already present and no cost is incurred.

Compute the minimum total cost required so that $[1,2,\dots,N]$ is a valid DFS order.

inputFormat

The first line contains an integer $N$ ($2 \leq N \leq 750$). This is followed by $\frac{N(N-1)}{2}$ integers representing $a_{i,j}$ for every pair $(i,j)$ with $1 \le i < j \le N$. The integers for each $i$ are given in order for $j=i+1, i+2, \dots, N$, separated by spaces or newlines.

outputFormat

Output a single integer: the minimum total cost to modify the graph so that $[1,2,\dots,N]$ is a valid DFS order.

sample

2
5

5