题目描述

给 $n$ 个数 $a_i$，再给你一个 $n\times n$ 的矩阵 $c$，无论是 $a$ 还是 $c$，都保证是整数。

现在你可以做一类操作：

• 将 $a_i$ 减一，$a_j$ 减一，花费 $c_{i,j}$ 的代价。$i,j$ 可以相同，相当于 $a_i$ 减 $2$。

现在要求把 $a_i$ 全部变成 $0$，问花费最少的代价是多少，无解输出 $-1$。

输入格式

从 match.in 读入数据。

第一行为一个正整数 $n$。

第二行为 $n$ 个整数 $a_i$。

接下来 $n$ 行，每行 $n$ 个数 $c_{i,j}$。

输出格式

输出到 match.out 中。

仅一行一个整数，表示最小的代价。

样例

样例 1

3
2 2 2
1 4 3
4 4 5
3 5 6

10

连续两次选择 $1,3$，然后选择 $2,2$，代价为 $4+3\times 2=10$。

样例 2

2
2 39
23 9
9 23

-1

样例 3

1
2
100

100

样例 4、5

为题目附件中 match*.in 与 match*.out。

数据范围与限制

对于所有数据，满足 $1\le n\le 50$，$0\le c_{i,j}\le 10^5$，$0\le a_i\le 100$ 且 $a_i$ 中至多有 $10$ 个奇数。