Description

小粉兔用集训队的奖金买下了一片地。

这片地上有 $n$ 个房子，有些房子之间有道路，有些房子之间则是杂草。

她可以花费一定的代价拆毁一条道路，或是啃光一片草使得两个房子间可以通行~~（大雾）~~。

她喜欢生成树，所以她要让所有道路形成一棵生成树。

求最小花费。 (提示：生成树：各节点均可以形成通路，但不能有环路存在，本题是带权边，求最小花费！ )

Input Format

从文件 rabbit.in 中读入。

第一行一个数，$n$。

接下来 $n$ 行，每行 $n$ 个数，代表 $a_{i,j}$。如果为正数，说明它们之间没有道路，需要 $a_{i,j}$ 的花费来修建；如果为负数，说明它们之间有道路，需要 $-a_{i,j}$ 的花费来拆毁。

Output Format

输出到文件 rabbit.out 中。

一行一个数，代表最小花费。

Sample

样例输入

3
0 1 -3
1 0 5
-3 5 0

样例输出

1

Hint

对于 $40\%$ 的数据，$n \leq 20$。
对于 $100\%$ 的数据，$5 \le n \leq 1000,1 \le |a_{i,j}(i \not = j) |\leq 1000$，保证所有 $a_{i, i} = 0$ 且 $a_{i,j}=a_{j,i}$。