匹配题

一般图最小权匹配，每个人都爱做。

题目描述

给定一个 $n\times n$ 的非负整数矩阵 $A$，其中 $i>j$ 的位置有 $A_{i,j}=0$。保证 $n$ 是偶数。

构造一张 $n$ 个点的完全图，点的编号分别为 $1,2,\cdots,n$。对于所有 $1\le i<j\le n$，添加一条连接 $i,j$ 的边，权值为：

$$\sum_{l=1}^{i}\sum_{r=i}^{j-1}A_{l,r}+\sum_{l=i+1}^{j}\sum_{r=j}^{n}A_{l,r}$$

求这张图的最小权完美匹配的权值。

对于带权无向图 $G=(V,E)$，设 $w(e)$ 为边 $e\in E$ 的权值，定义 $G$ 的最小权完美匹配的权值为：所有满足 $M\subseteq E$，且使得任意 $u\in V$ 在 $M$ 中有恰好一条相邻边的集合 $M$ 中 $\sum_{e\in M}w(e)$ 的最小值。

输入格式

第一行包含一个偶数 $n$（$2\le n\le 1500$）。

接下来 $n$ 行，第 $i$ 行包含 $n-i+1$ 个非负整数表示 $A_{i,i},A_{i,i+1},\cdots,A_{i,n}$。

对于所有 $1\le i\le j\le n$，保证 $0\le A_{i,j}\le 10^9$。

输出格式

输出一个整数，表示构造出的完全图的最小权完美匹配的权值和。

样例

样例输入 1

4
1 1 1 1
1 1 1
1 1
1

样例输出 1

8

样例输入 2

6
1 1 4 5 1 4
1 9 1 9 8
1 0 1 1
4 5 1
4 1
9

样例输出 2

52