Kleofáš sa vlúpal do základne KSP, aby z organizátorských serverov ukradol zadania ďalšej série (ktoré už sú samozrejme dávno pripravené). Ale spustil sa alarm a do T2 už mieria vytočení rooti, takže Kleofáš si musí pohnúť a všetky príklady ukradnúť čo najrýchlejšie.

Úloha

Na serveri je $$n$$ príkladov. Kleofáš chce všetky stiahnuť na svoj notebook. Stiahnuť príklad číslo $$i$$ trvá $$d_{i,i}$$ sekúnd. Ale ak sa podobá na nejaký už stiahnutý príklad $$j$$, netreba ho sťahovať celý – stačí za $$d_{i,j}$$ sekúnd stiahnuť rozdiely medzi nimi.

Príklady je možné sťahovať v ľubovoľnom poradí. Zistite, za koľko sekúnd dokáže Kleofáš stiahnuť všetky príklady.

Formát vstupu

V prvom riadku vstupu je číslo $$n$$ ($$1\leq n \leq 1\,000$$) udávajúce počet príkladov. Nasleduje $$n$$ riadkov s $$n$$ číslami, z čoho $$j$$-te číslo $$i$$-teho riadku je hodnota $$d_{i,j}$$ ($$1\leq d_{i,j} \leq 10^9$$). Pre $$i=j$$ je to čas prenosu celého príkladu, zatiaľčo pre $$i\neq j$$ je to čas prenosu rozdielov medzi príkladmi $$i$$ a $$j$$. Platí, že pre každé $$i,j$$ je $$d_{i,j}=d_{j,i}$$.

Formát výstupu

Vypíšte, koľko sekúnd treba na stiahnutie všetkých príkladov.

Príklad

Input:

5
4 7 7 6 7
7 11 4 3 4
7 4 8 7 6
6 3 7 1 5
7 4 6 5 5

Output:

16

Najprv stiahneme celý štvrtý príklad, potom jeho rozdiely od druhého, a keď už máme druhý, stiahneme jeho rozdiely od tretieho a piateho príkladu. Prvý príklad tiež stiahneme celý, lebo sa veľmi nepodobá na žiaden iný.