Farmer John leva água aos $N$ pastos ($1 \le N \le 300$), numerados $1,\ldots,N$. Pode construir um poço ou conectar por cano a outro pasto que já tenha água.

Poço em $i$ custa $W_i$ ($1 \le W_i \le 100,000$). Cano entre $i$, $j$ custa $P_{ij}$ ($1 \le P_{ij} \le 100,000; P_{ij}=P_{ji}; P_{ii}=0$).

Determine o menor custo de abastecer todos.

Entrada

• Linha 1: inteiro $N$.
• Linhas $2,\ldots,N+1$: a linha $i+1$ contém inteiro $W_i$.
• Linhas $N+2,\ldots,2N+1$: a linha $N+1+i$ contém $N$ inteiros separados por espaços; o $j$-ésimo é $P_{ij}$.

Saída

• Linha 1: inteiro, custo mínimo de abastecer todos.

Exemplos

Entrada 1

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

Saída 1

9

Nota

Quatro pastos: poço em 1 custa 5, em 2 e 3 custa 4, em 4 custa 3. Canos custam 2, 3, 4 conforme as ligações.

Um poço em 4 e conectar cada pasto ao 1 custa $3+2+2+2=9$.

Subtarefas

Pontos: 400

Créditos do problema: Paul Christiano, 2007