Farmer John снабжает водой $N$ пастбищ ($1 \le N \le 300$), пронумерованных $1,\ldots,N$. Можно выкопать колодец или соединить трубой с другим пастбищем, где вода уже есть.

Колодец на $i$ стоит $W_i$ ($1 \le W_i \le 100,000$). Труба между $i$, $j$ стоит $P_{ij}$ ($1 \le P_{ij} \le 100,000; P_{ij}=P_{ji}; P_{ii}=0$).

Найдите минимальную цену воды для всех.

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

• Строка 1: целое $N$.
• Строки $2,\ldots,N+1$: строка $i+1$ содержит целое $W_i$.
• Строки $N+2,\ldots,2N+1$: строка $N+1+i$ содержит $N$ целых через пробел, $j$-е — $P_{ij}$.

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

• Строка 1: целое, минимальная цена снабжения всех пастбищ.

Примеры

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

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

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

9

Примечание

Четыре пастбища: колодец на 1 стоит 5, на 2 и 3 — 4, на 4 — 3. Трубы стоят 2, 3, 4 в зависимости от концов.

Можно выкопать на 4 и соединить каждое с 1 за $3+2+2+2=9$.

Подзадачи

Баллы: 400

Автор задачи: Paul Christiano, 2007