V krajine je $n$ miest očíslovaných celými číslami $1$ až $n$, do ktorých treba priviesť pitnú vodu. Vodu môžeme do mesta priviesť buď tak, že v meste vykopeme studňu s filtračnou stanicou, alebo spojíme mesto potrubím s iným mestom, ktoré už má privedenú pitnú vodu.
Vykopať v meste s číslom $i$ studňu stojí $S_i$ peňazí. Postaviť obojsmerné potrubie medzi mestami $i$ a $j$ stojí $P_{i,j}$. Zistite, za koľko najmenej peňazí sa dá priviesť voda do všetkých miest.
Na prvom riadku je číslo $n$ ($1 \leq n \leq 300$) — počet miest.
Nasleduje $n$ riadkov, na $i$-tom z nich je $S_i$ ($1\leq S_i\leq 100\,000$).
Napokon je na vstupe $n$ riadkov a na každom z nich je $n$ čísel oddelených medzerami $j$-te číslo na $i$-tom riadku je $P_{i,j}$ ($1\leq P_{i,j}\leq 100\,000$, $P_{i,j} = P_{j,i}$, $P_{i,i} = 0$).
Vypíšte jedno číslo — najmenšie množstvo peňazí, za ktoré sa dá priviesť voda do všetkých miest. Nezabudnite výstup ukončiť znakom konca riadku (\verb'\n').
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
9
V 4. meste vykopeme studňu a postavíme potrubia medzi mestami 4-1, 1-3, 1-2. Bude nás to stáť $3 + 2 + 2 + 2 = 9$ peňazí.