D. Хачирхалтай тосгон

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Володя саяхан маш сонин тосгонд зочилжээ. Тус тосгонд $N$ тооны жуулчдын үзвэрийн газар байх ба бүгд хоорондоо хоёр урсгалтай замаар холбогдсон байна. Зам тус бүрээр зорчих ба төлбөр нь (натурал тоо) бүгд өөр өөр байдаг.

Гэвч энэ тосгоны хамгийн гайхалтай зүйл нь бүх хотын үзвэрийн газрын төлбөр ижил байгаа явдал юм. Тиймээс хэрэв бид хотын бүх үзвэрийн газраар яг нэг удаа орж үзэх боломжтой маршрут зохиовол маршрут бүр зөвхөн сонгосон замуудаасаа хамааран өөр өөр үнэтэй байна.

Володя таныг замын бүх хөлс нь үргэлж 1000-аас ихгүй байх тийм үнийн тогтолцоо олж чадах эсэхийг сонирхож байна.

Оролт

Оролтын мөр нь ($3 ≤ N ≤ 20$) гэсэн ганц натурал тоо агуулах ба энэ нь тосгон дахь үзвэрийн газрын тоог илэрхийлнэ.

Гаралт

Гаралт нь $N$ мөр агуулах ба мөр бүр нь $N$ эерэг бүхэл тоо агуулах ёстой. Энэ нь матриц хэлбэрээр өгөгдсөн үнийн график юм. $i$-р мөрний $j$-р тоо нь $j$-р мөрний $i$-р тоотой тэнцүү үнэтэй байна. Диагоналийн элементүүд бүгд тэг байна. Бүх тоо $1000$-аас хэтрэхгүй. Бүх үнэ нь эерэг ба хос хосоороо ижил байна. Хэрэв хэд хэдэн хариу олдож байвал алийг нь ч хэвлэсэн болно.

Орчуулсан: Даариймаа, Энхгэрэл

Жишээ тэстүүд

Оролт
3
Гаралт
0 3 4 
3 0 5 
4 5 0 
Сэтгэгдлүүдийг ачааллаж байна...