题目背景

一座大型调度中心正在维护两组规模相同的设备：左侧是任务节点，右侧是执行节点。某些任务可以交给某些执行节点处理，每条可用连接都有不同的维护成本。

为了进行一次容灾演练，工程师需要暂时断开一部分连接，使得系统中不再存在能够让所有任务与所有执行节点一一对应的完整分配方案。断开连接的数量并不重要，但希望断开的连接总成本尽可能小。

请你计算完成这次演练所需的最小总代价。

题目描述

给定一个带权二分图。二分图左右两部分各有 $n$ 个顶点，均编号为 $1,2,\ldots,n$。

图由一个 $n\times n$ 的字符矩阵 $A$ 表示：

• 若 $A_{i,j}=\texttt{0}$，表示左部顶点 $i$ 与右部顶点 $j$ 之间没有边；
• 若 $A_{i,j}$ 是 1 到 9 之间的数字，则表示二者之间存在一条边，其权值为该数字对应的整数。

一个完美匹配是由 $n$ 条边组成的集合，使得左右两部分的每个顶点都恰好与其中一条边相连。等价地，它可以表示为一个 $1$ 到 $n$ 的排列 $p$，并且对每个 $i$，边 $(i,p_i)$ 都存在。

你可以删除图中的任意若干条边。删除一条边需要支付等于该边权值的代价。

求使剩余图中不存在完美匹配所需的最小总代价。

输入格式

第一行包含一个整数 $n$。

接下来 $n$ 行，每行包含一个长度为 $n$ 的字符串，表示矩阵 $A$。

输出格式

输出一个整数，表示使图中不存在完美匹配所需的最小总代价。

样例 1

1
1

1

样例解释

图中只有一条边，必须将其删除。

样例 2

1
0

0

样例解释

原图本身就没有完美匹配，因此不需要删除任何边。

样例 3

2
44
44

8

样例 4

3
861
870
245

6

样例 5

5
01000
30200
11102
10001
11001

0

数据范围

对于所有测试数据：

• $1\le n\le 20$；
• 每个 $A_{i,j}$ 都是字符 0 到 9；
• 0 表示不存在对应边，而不是一条权值为 $0$ 的边。

时间限制

$2\ \text{s}$

空间限制

$256\ \text{MiB}$