Задача №114860. Приготовление еды
Степан и Сергей поступили в университет. Началась взрослая жизнь, а значит, теперь им нужно готовить еду самостоятельно.
Друзья умеют готовить \(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\) раз.
В первом примере оптимально приготовить следующие пары блюд: \((1, 3)\), \((1, 3)\), \((2, 2)\).
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