G. Приготовление еды
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Степан и Сергей поступили в университет. Началась взрослая жизнь, а значит, теперь им нужно готовить еду самостоятельно.

Друзья умеют готовить $$$n$$$ различных блюд. Купив все необходимые продукты, ребята поняли, что до следующего похода в магазин они хотят приготовить $$$i$$$-е блюдо ровно $$$a_i$$$ раз.

Каждый день Сергей и Степан выбирают два блюда $$$i$$$ и $$$j$$$ и готовят их, это занимает $$$c_{i, j}$$$ единиц времени. При этом возможна ситуация, когда $$$i=j$$$, тогда в этот день $$$i$$$-е блюдо оказывается приготовлено дважды.

Поскольку ребята довольно ленивые, они хотят минимизировать суммарное время приготовления блюд за все дни до следующего похода в магазин. Помогите им в этом!

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10$$$) — количество блюд, которые ребята умеют готовить.

Вторая строка содержит $$$n$$$ положительных целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 50$$$) — для каждого блюда указано, сколько раз его нужно приготовить.

В каждой из следующих $$$n$$$ строк записаны $$$n$$$ целых чисел $$$c_{i, j}$$$ ($$$1 \le c_{i, j} \le 100$$$), $$$j$$$-е число в $$$i$$$-й строке обозначает время приготовления пары блюд $$$i$$$ и $$$j$$$. Гарантируется, что $$$c_{i, j}=c_{j, i}$$$.

Выходные данные

Выведите одно целое число: минимальное суммарное время приготовления блюд либо $$$-1$$$, если невозможно составить план приготовления блюд так, чтобы $$$i$$$-е было приготовлено ровно $$$a_i$$$ раз.

Примеры
Входные данные
3
2 2 2
1 4 3
4 4 5
3 5 6
Выходные данные
10
Входные данные
2
2 39
23 9
9 23
Выходные данные
-1
Входные данные
1
2
100
Выходные данные
100
Примечание

В первом примере оптимально приготовить следующие пары блюд: $$$(1, 3)$$$, $$$(1, 3)$$$, $$$(2, 2)$$$.