+ محدودیت زمان: ۴ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آقای پنگ، رئیس کل زندان اوین است. در این زندان $n$ خلاف‌کار در بند هستند و از $1$ تا $n$ شماره‌گذاری شده‌اند. میزان ارتباط دو زندانی $i$ و $j$ برابر با $a_{i,j}$ است. امروز با آقای پنگ تماس اضطراری گرفته‌اند و به او گفته‌اند که تا ۲۴ ساعت آینده، بمبی در این زندان منفجر خواهد شد. او باید هر چه سریع‌تر زندانیان را جابجا کند. او باید زندانیان را تا رفع خطر به یکی از دو جزیره نخیلو و مولیات تبعید کند. قدرت افراد تبعید شده به یک جزیره، برابر با بیشینه‌ میزان ارتباط بین هر جفت آن‌هاست. به صورت دقیق‌تر اگر مجموعه $S$ زندانیان تبعید شده به یک جزیره باشند، قدرت آن‌ها برابر با $\max_{i,j \in S} a_{i,j}$ خواهد بود (اگر $|S| \le 1$ قدرت آن جزیره صفر خواهد بود). به آقای پنگ کمک کنید که طوری زندانیان را بین دو جزیره تقسیم (و تبعید) کند که جمع قدرت افراد جزیره نخیلو و قدرت افراد جزیره مولیات کمینه شود. . # ورودی در سطر اول $n$، تعداد زندانیان آمده‌است. سپس در $i$ امین سطر از $n$ سطر بعدی، $n-i$ عدد آمده‌است که $j$ امین عدد برابر با $a_{i,j+i}$ است. همچنین $a_{i+j,i} = a_{i,i+j}$ $$1 \le n \le 200$$ $$0 \le a_{i,j} \le 10^9$$ # خروجی در تنها سطر خروجی کمترین قدرت زندانیان را پس از تبعید چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت | |:-------:|:----------:|:-----------:| |۱ | ۱۳ | $n \le 20$ | |۲| ۶۴ | $n \le 50$ | |۳| ۲۳ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 5 4 5 0 2 1 3 7 2 0 4 ``` ## خروجی نمونه ۱ ``` 4 ``` ## ورودی نمونه ۲ ``` 7 1 10 5 5 5 5 5 10 5 5 5 100 100 5 5 10 5 5 98 99 3 ``` ## خروجی نمونه ۲ ``` 15 ```