Farmer John versorgt $N$ Weiden ($1 \le N \le 300$), nummeriert $1,\ldots,N$, mit Wasser. Er baut einen Brunnen oder verbindet mit einem Rohr zu einer anderen bereits versorgten Weide.

Brunnen auf $i$ kostet $W_i$ ($1 \le W_i \le 100,000$). Rohr zwischen $i$, $j$ kostet $P_{ij}$ ($1 \le P_{ij} \le 100,000; P_{ij}=P_{ji}; P_{ii}=0$).

Bestimme die minimalen Kosten zur Versorgung aller.

Eingabe

• Zeile 1: ganze Zahl $N$.
• Zeilen $2,\ldots,N+1$: Zeile $i+1$ enthält die ganze Zahl $W_i$.
• Zeilen $N+2,\ldots,2N+1$: Zeile $N+1+i$ enthält $N$ durch Leerzeichen getrennte ganze Zahlen; die $j$-te ist $P_{ij}$.

Ausgabe

• Zeile 1: ganze Zahl, minimale Kosten der Versorgung aller Weiden.

Beispiele

Eingabe 1

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

Ausgabe 1

9

Hinweis

Vier Weiden: Brunnen auf 1 kostet 5, auf 2 und 3 je 4, auf 4 kostet er 3. Rohre kosten je nach Weiden 2, 3, 4.

Brunnen auf 4 und Verbindung jeder Weide mit 1 kosten $3+2+2+2=9$.

Teilaufgaben

Punkte: 400

Aufgabenautor: Paul Christiano, 2007