7. Ohavný čin

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ý.