Во некоја држава, по спроведувањето на национално помирување помеѓу сите политички партии, било одлучено да се изгради нова патна мрежа помеѓу сите N градови, така што сите градови ќе бидат меѓусебно поврзани (или преку директен пат помеѓу два града, или индиректно – преку патишта кои поминуваат низ други градови). Сите патишта ќе бидат двонасочни.

За таа цел, тие ангажирале експерт кој ги испланирал патиштата. Како резултат, тој презентирал матрица составена од N*N вредности Sij, каде што секоја вредност Sij го означува најкраткото растојание од градот i до градот ј (низ новите патишта).

За жал, не сме сигурни дали оваа матрица била соодветно препишана од страна на вработените во тамошната Агенција за патишта. За дадена матрица Sij составена од N*N вредности, напишете програма која ќе отпечати “GRESHKA” доколку не може да постои патна мрежа која ги поврзува сите N градови со најкратки растојанија помеѓу градовите како што е дадено во матрицата; или ќе ја отпечати вкупната должина на сите патишта во мрежата. Доколку постојат повеќе решенија, отпечатете ја најмалата можна вкупна должина.

(Разгледајте го примерот даден во продолжение за повеќе информации)

Влез

Во првиот ред е запишан еден цел број N (3 <= N <= 300), кој го означува бројот на градови. Во секој од наредните N редови се запишани по N вредности Sij (1 <= Sij <= 1 000 000 000), кои го означуваат најкраткото растојание помеѓу градовите i и j. Притоа, секогаш ќе важи дека Sij = Sji (најкраткото растојание од градот i до ј е еднакво на најкраткото растојание од градот ј до i).

Растојанието од градовите до самите себеси ќе биде означено со вредност 0 (т.е. сите елементи од главната дијагонала на матрицата ќе бидат Sii = 0).

Излез

Отпечатете ја најмалата вкупна должина на сите патишта; или “GRESHKA” доколку таква патна мрежа не може да се состави.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
3
0 6 4
6 0 2
4 2 0

излез
6

влез
3
0 5 2
5 0 2
2 2 0

излез
GRESHKA

Објаснување за првиот пример: Постои пат (со должина 4км) од градот 1 до градот 3, и пат (со должина 2км) од градот 2 до градот 3. Вкупната должина на патната мрежа е 6км (па тоа е излезот).

Градовите 1 и 2 не мора да се поврзани со директен пат. Во матрицата е запишано дека најкраткото растојание помеѓу нив е 6, бидејќи постои пат кој почнува од градот 1, поминува низ градот 3 и завршува во градот 2 со должина 6км (4+2=6).


Објаснување за вториот пример: Не е можно да се состави патна мрежа каде што вредностите во матрицата ќе го претставуваат најкраткото растојание помеѓу градовите.