Stephen 和 Sergey 在大学注册并住在校园里。现在他们需要学习做饭。 朋友们学会了烹饪 $n$ 种不同的菜肴。在购买了所有必要的食物后，他们决定在下次购物前，将第 $i$ 道菜恰好烹饪 $a_i$ 次。

每天，Sergey 和 Stephen 会选择两道菜 $i$ 和 $j$ 进行烹饪，烹饪耗时为 $c_{i,j}$。可能出现 $i = j$ 的情况，这意味着第 $i$ 道菜在当天被烹饪了两次。

他们非常懒，所以想在下次购物前，使所有烹饪的总时间最小化。请帮帮他们！

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10$)，表示他们可以烹饪的菜肴数量。 第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 50$)，表示每道菜需要烹饪的次数。 接下来的 $n$ 行包含 $n$ 个空格分隔的整数 $c_{i,j}$ ($1 \le c_{i,j} \le 100$)，第 $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

输出 1

10

输入 2

2
2 39
23 9
9 23

输出 2

-1

输入 3

1
2
100

输出 3

100

说明

在第一个测试用例中，最优的烹饪方案是烹饪以下几对菜肴：$(1, 3), (1, 3), (2, 2)$。