C. Үдэшлэг

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

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

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

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

Note the unusual memory limit for the problem.

Нэгэн байгууллагийн ажилчид баасан болон хагассайны шөнө үдэшлэгт явцгаадаг байв. Уг байгууллага $N$ ажилчинтай ба хотод $N$ шөнийн клуб байдаг. Гэхдээ тухайн байгууллагын нэгээс олон ажилчид нэг шөнийн клубт таарвал тухайн үдэшлэг зодооноор дуусч ихээхэн хохирол учруулдаг учраас урьдчилан сэргийлэхийн тулд тухайн байгууллагын ямар ч хоёр ажилчинг ижил долоо хоногт нэг адилхан клубт орохыг захирал нь хориглосон.

Чи ажилчдын үдэшлэгийг захирлын тушаалаар зохион байгуулахаар болсон ба чамд захирал ажилчин бүрийн аль клубт баасан болон хагассайнд ороход хэр их дуртай болохыг тоон утгаар илэрхийлсэн сэтгэл ханамжийн статистик мэдээллийг өгсөн.

Нийт ажилчдын тэн хагас нь баасан гаригт, үлдсэн хагас нь хагассайнд гарч байхаар тааруулах ёстой ба хэрэв чи тэдний сэтгэл ханамжийн стастик тоон утгын нийт нийлбэр боломжит хамгийн их байхаар хүмүүсийг хуваарилч чадвал шагнагдана.

Оролт

Эхний мөрөнд тухайн байгууллагын ажилчдын тоо болох $N$-г оруул.

Тэгээд $N × N$ матрицыг оруул. Энэ матрицын $i$-р мөр ба $j$-р баганы элемент нь $i$-р хүн $j$-р клубт баасан гаригт явахад хэр их дуртай байх утгыг илэрхийлнэ.

Дараа нь хагассайнд хүмүүсийн авч чадах сэтгэл ханамжийг мөн адилаар илэрхийлсэн $N × N$ матрицыг оруул. * $2 ≤ N ≤ 20$ * $N$ тэгш * $0 ≤ $ сэтгэл ханамжийн илэрхийлэл $ ≤ 10^{6}$ * Бүх утга бүхэл

Гаралт

Боломжит сэтгэл ханамжийн хамгйин их утгыг илэрхийлсэн ганц бүхэл тоог хэвлэ.

Орчуулсан: Э.Оргил-Эрдэнэ

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

Оролт
4
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
5 8 7 1
6 9 81 3
55 78 1 6
1 1 1 1
Гаралт
167

Тэмдэглэл

Хэрхэн хүмүүсээ хуваарилж болохыг харуулъя:

Баасан гаригт: эхний хүн 4дэх клубт(сэтгэл ханамж 4) ба 4дэх хүн эхний клубт(сэтгэл ханамж 4)

Хагассайнд: 2дахь хүн 3дэх клубт(сэтгэл ханамж 81) ба 3дахь хүн 2дэх клубт орно (сэтгэл ханамж 78).

4+4+81+78 = 167

Сэтгэгдлүүдийг ачааллаж байна...