Farmer John apporte de l’eau à $N$ pâturages ($1 \le N \le 300$), numérotés $1,\ldots,N$. Creusez un puits sur place ou raccordez par un tuyau à un autre pâturage ayant déjà de l’eau.

Un puits en $i$ coûte $W_i$ ($1 \le W_i \le 100,000$). Un tuyau entre $i$, $j$ coûte $P_{ij}$ ($1 \le P_{ij} \le 100,000; P_{ij}=P_{ji}; P_{ii}=0$).

Trouvez le coût minimal pour tous les alimenter.

Entrée

• Ligne 1 : entier $N$.
• Lignes $2,\ldots,N+1$ : la ligne $i+1$ contient l’entier $W_i$.
• Lignes $N+2,\ldots,2N+1$ : la ligne $N+1+i$ contient $N$ entiers séparés par des espaces ; le $j$-ième est $P_{ij}$.

Sortie

• Ligne 1 : entier, coût minimal pour tout alimenter.

Exemples

Entrée 1

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

Sortie 1

9

Remarque

Quatre pâturages : puits en 1 pour 5, en 2 et 3 pour 4, en 4 pour 3. Les tuyaux coûtent 2, 3, 4 selon les raccordements.

Un puits en 4 et des raccordements de chaque pâturage au 1 coûtent $3+2+2+2=9$.

Sous-tâches

Points : 400

Auteur du problème : Paul Christiano, 2007