题目描述

Stephen 和 Sergey 上了大学并住在校园里。现在他们需要学会做饭。

他们已经学会做 n 种不同的菜。买完食材后，他们决定在下一次购物前，第 i 种菜恰好要做 $a_i$ 次。

每天 Sergey 和 Stephen 会选择两道菜 i 和 j 来做，耗时为 $c_{i,j}$。可以有 $i=j$，这表示当天同一道菜做两次。

他们很懒，所以希望在下一次购物前完成所有做饭计划的总耗时最小。请你帮助他们。

输入格式

第一行输入整数 n，表示菜的种类数。

第二行输入 n 个正整数：

表示每种菜必须做的次数。

接下来 n 行，每行 n 个整数。第 i 行第 j 个数为 $c_{i,j}$，表示同一天做菜 i 和菜 j 所需时间。

保证 $c_{i,j}=c_{j,i}$。

输出格式

输出一个整数，表示最小总做饭时间。

如果无法制定计划，使得第 i 种菜恰好做 $a_i$ 次，则输出 -1。

样例

样例 1

样例输入：

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

样例输出：

10

样例 2

样例输入：

2
2 39
23 9
9 23

样例输出：

-1

样例 3

样例输入：

1
2
100

样例输出：

100

样例说明

在第一个样例中，最优方案是做如下三天：

总耗时为 $3+3+4=10$。