Farmer John abastece $N$ pastos ($1 \le N \le 300$), numerados $1,\ldots,N$. Puede construir un pozo o conectar con tubería a otro pasto que ya tenga agua.

Un pozo en $i$ cuesta $W_i$ ($1 \le W_i \le 100,000$). Una tubería entre $i$, $j$ cuesta $P_{ij}$ ($1 \le P_{ij} \le 100,000; P_{ij}=P_{ji}; P_{ii}=0$).

Determina el mínimo coste para abastecer todos.

Entrada

• Línea 1: entero $N$.
• Líneas $2,\ldots,N+1$: la línea $i+1$ contiene entero $W_i$.
• Líneas $N+2,\ldots,2N+1$: la línea $N+1+i$ contiene $N$ enteros separados por espacios; el $j$-ésimo es $P_{ij}$.

Salida

• Línea 1: entero con el coste mínimo para abastecer todos.

Ejemplos

Entrada 1

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

Salida 1

9

Nota

Cuatro pastos: pozo en 1 cuesta 5, en 2 y 3 cuesta 4, en 4 cuesta 3. Las tuberías cuestan 2, 3, 4 según los pastos.

Un pozo en 4 y conectar cada pasto al 1 cuesta $3+2+2+2=9$.

Subtareas

Puntos: 400

Autor del problema: Paul Christiano, 2007