Masala #0943

Logistikada ham, kam emas hollarda muammolariga yechimni dasturlash va algoritmlar orqali topib berish mumkin. Quyidagi muammoga ham yechim topib ko`ring.

Bir mamlakatda $N$ ta shahar va har bir shaharlarni o`zaro bog`lovchi bir tomonlama yo`llar mavjud. Har bir yo`l o`z kengligiga ega. Logistika firmasining yangi loyihasiga ko`ra, bu davlatda har bir shahardan barcha boshqa shaharlarga yuk mashinalari mahsulotga to`ldirilib jo`natiladi.

Muammo shundaki, sig`imi $x$ miqdorli mahsulot olib o`tadigan yuk mashinasi, $y$ kenglikdagi yo`ldan o`tishi uchun, $x \leq y$ shart bajarilishi shart. Ammo firmaning ustaviga ko`ra barcha yuk mashinalarini bir xil sig`imda bo`lishi lozim.

Ushbu mamlakatda firma har bir shahardan boshqa ixtiyoriy shaharga yuk mashinasi orqali mahsulot olib o`ta olish sharti bilan yuk mashinalarining eng katta sig`imini toping.

Yagona qatorda bitta butun son $N(1 \leq N \leq 300)$ kiritiladi.

Keyingi $n$ ta qatorning har birida $N$ tadan natural son - o`lchami $N$ bo`lgan butun sonlardan iborat kvadrat matritsa kiritiladi. Matritsadagi $i$-ustun, $j$-qatorda joylashgan son, $i$-shahardan $j$-shaharga boruvchi yo`lning kengligi kiritladi.

Yagona qatorda bitta butun son ushba mamlakatda firma loyihasini o`tkazishi mumkin bo`lgan yuk mashinalarining eng katta sig`imini chiqaring.