Hardtown 是一个包含 $N$ 个城镇的城市，城镇编号从 $1$ 到 $N$。前任市长在每两个城镇之间都修建了一条单向道路。换句话说，对于任意两个不同的城镇 $i$ 和 $j$，存在一条道路，你可以从 $i$ 到 $j$ 或者从 $j$ 到 $i$ 通行，但不能同时双向通行。

由于城市规划不当，你怀疑可能存在两个不同的城镇，使得你无法通过一条或多条道路从其中一个城镇到达另一个城镇。作为新任市长，你必须解决这个问题。不幸的是，没有足够的空间将每条道路改为双向，也不能修建新道路。因此，你决定反转某些道路的方向。

对于每一对城镇，已知道路的初始方向以及反转该方向所需的成本。你可以反转零条或多条道路的方向。操作完成后，你必须能够通过道路从任意一个城镇到达其他任何城镇。你的任务是计算实现这一目标所需的最小总成本。在问题的约束条件下，可以证明一定存在解决方案。

输入格式

第一行包含一个整数 $N$（$3 \le N \le 3000$），表示城市中的城镇数量。

接下来的 $N-1$ 行中，第 $i$ 行包含 $N-i$ 个非零整数 $c_{i,i+1}, c_{i,i+2}, \dots, c_{i,N}$，每个整数的绝对值在 $10^9$ 以内。对于每对 $i$ 和 $j$（$1 \le i < j \le N$），$c_{i,j}$ 表示城镇 $i$ 和 $j$ 之间道路的信息。如果 $c_{i,j}$ 为正，则初始时你只能从 $i$ 到 $j$ 通行。否则，初始时你只能从 $j$ 到 $i$ 通行。在任何情况下，绝对值 $|c_{i,j}|$ 都是反转该道路方向的成本。

输出格式

输出一行，包含一个整数：使得你可以从任意城镇到达其他任何城镇所需反转道路的最小总成本。

样例

输入 1

7
-17 -76 -46 -94 83 -22
53 -59 95 42 82
-31 66 26 12
71 96 56
65 -29
-23

输出 1

57

输入 2

7
-17 -76 -46 -94 83 -22
53 -59 95 42 82
31 66 -26 12
71 96 56
65 -29
-23

输出 2

0