И Бидик мора да собере потписи од N претседатели на држави. Заради анонимност, секој од главните градови каде што се претседателите ќе го означиме едноставно со различен број, еден од 1, 2, ..., N. Знаеме дека има директни летови меѓу секои два града. Знаеме секој лет колку трае, па Бидик сака само по еднаш да отиде во секој од градовите и притоа да потроши најмалку време за летање.

Но, има уште еден услов. Кога ќе се најде во градот означен со K тој ќе добие потпис од тамошниот претседател или ако сите претседатели од градовите со ознаки помали од K веќе се потпишале, или ниту еден од нив до тогаш не се потпишал. Со други зборови, тој не може дел од тие градови да ги посети пред, а дел после K-тиот град.

Помогнете му на Бидик да ги собере потписите за петицијата со цел да му се исполни животната желба да се пребои Месечината виолетово, и пресметајте колку ќе биде вкупното време на летање, за да се посетат сите градови, почнувајќи од кој било и завршувајќи во кој било град, но притоа внимавајќи секој претседател да се потпише според чудниот услов што го има секој од нив.

Влез

Во првиот ред има еден позитивен цел број N (2 ≤ N ≤ 1500), бројот на градови.
Во секој од следните N редови има по N позитивни цели броеви од интервалот [0, 1000]. Бројот на B-тата позиција во A-тата редица ја претставува должината на летот меѓу градовите A и B; овој број е секако еднаков со A-тиот број во B-тата колона. Кога A = B, тој број е 0. Во спротивно, тоа е позитивен број.

Забелешка.
Во подзадача 1, за 28 поени: N ≤ 10.
Во подзадача 2, за 17 поени: N ≤ 17.
Во подзадача 3, за 55 поени: нема дополнителни ограничувања.

Излез

Во единствениот ред отпечатете еден број, бараната минимална тотална должина на летањето.

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

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

Примери

влез
3
0 7 1
7 0 5
1 5 0

излез
8

влез
4
0 13 6 9
13 0 16 10
6 16 0 11
9 10 11 0

излез
29

Објаснување за првиот пример: оптималната секвенца за посети е 2, 1, 3 или 3, 1, 2. Секвенцата 1, 3, 2 е уште пократка, но не го исполнува претседателскиот услов.

Објаснување за вториот пример: секвенцата за посети е или 3, 1, 2, 4 или 4, 2, 1, 3.