Farmer John porta acqua ai $N$ pascoli ($1 \le N \le 300$), numerati $1,\ldots,N$. Può costruire un pozzo o collegare con tubo un altro pascolo già rifornito.

Pozzo in $i$ costa $W_i$ ($1 \le W_i \le 100,000$). Tubo tra $i$, $j$ costa $P_{ij}$ ($1 \le P_{ij} \le 100,000; P_{ij}=P_{ji}; P_{ii}=0$).

Determina il minimo costo per rifornire tutti.

Input

• Riga 1: intero $N$.
• Righe $2,\ldots,N+1$: la riga $i+1$ contiene intero $W_i$.
• Righe $N+2,\ldots,2N+1$: la riga $N+1+i$ contiene $N$ interi separati da spazi; il $j$-esimo è $P_{ij}$.

Output

• Riga 1: intero, minimo costo per rifornire tutti.

Esempi

Input 1

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

Output 1

9

Note

Quattro pascoli: pozzo in 1 costa 5, in 2 e 3 costa 4, in 4 costa 3. Tubi costano 2, 3, 4 a seconda dei pascoli.

Pozzo in 4 e collegare ogni pascolo al 1 costa $3+2+2+2=9$.

Sottoproblemi

Punti: 400

Autore del problema: Paul Christiano, 2007