21639번 - Cooking 다국어

문제

Stephen and Sergey are enrolled at the university and live on campus. So now they need to learn to cook.

The friends have learned to cook $n$ different dishes. After buying all the necessary food, the guys have decided that before they go shopping next time, they will cook the $i$-th dish exactly $a_i$ times.

Each day Sergey and Stephen choose two dishes $i$ and $j$ and cook them, cooking takes $c_{i, j}$ units of time. It's possible that $i=j,ドル that means that the $i$-th dish is cooked twice on that day.

The guys are quite lazy, so they want to minimize the total cooking time for all the days before the next shopping. Help them to do it!

입력

The first line contains a single integer $n$ (1ドル \le n \le 10$) --- the number of dishes that the guys can cook.

The second line contains $n$ positive integers $a_1, a_2, \ldots, a_n$ (1ドル \leq a_i \leq 50$) --- the number of times it must be cooked for each dish.

The next $n$ lines contain $n$ space separated integers $c_{i, j}$ (1ドル \le c_{i, j} \le 100$), the $j$-th number in the $i$-th line denotes cooking time of pair of dishes $i$ and $j$. It is guaranteed that $c_{i, j}=c_{j, i}$.

출력

Print one integer: the minimum total time of cooking, or $-1,ドル if it is impossible to make a cooking plan such that the $i$-th dish is cooked exactly $a_i$ times.

제한

힌트

In the first test case it is optimal to cook the following pairs of dishes: $(1, 3),ドル $(1, 3),ドル $(2, 2)$.