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

Түүнд $n × n$ шатрын хѳлѳг байгаа. Нүд бүрт нь тоо бичсэн байв. Гаргари хѳлѳг дээр хоёр тэмээг хоюуланд нь идэгдэх нүд байхгүй байхаар байрлуулахыг хүсч байна. Тэмээнд идэгдэх нүднүүд дээрх тоонуудын нийлбэртэй тэнцүү хэмжээний долларыг Гаргари авна. Хэрхэн байрлуулбал хамгийн их доллар авахыг Гаргарид хэлнэ үү.

Тэмээнд идүүлэх нүд гэж тэмээтэй нэг диагональд оршиж байгаа нүднүүдийг хэлнэ (тэмээний байрлаж байгаа нүдийг түүнд идэгдэх нүд гэж үзнэ).

Оролт

Эхний мѳр $n$ $(2 ≤ n ≤ 2000)$ бүхэл тоог агуулна. Дараагийн $n$ мѳр бүр хѳлгийн нүднүүд дэх тоог илэрхийлэх $n$ ширхэг бүхэл тоо $a_{ij}$ $(0 ≤ a_{ij} ≤ 10^{9})$ агуулна.

Гаралт

Эхний мѳрѳнд Гаргарийн олж болох хамгийн их долларын хэмжээг хэвлэнэ. Дараагийн мѳрѳнд уг долларыг олохын тулд хэрхэн байрлуулахыг заах дѳрвѳн бүхэл тоо $x_{1}, y_{1}, x_{2}, y_{2}$ $(1 ≤ x_{1}, y_{1}, x_{2}, y_{2} ≤ n)$ хэвлэ, энд $x_{i}$, $y_{i}$ нь $i$-р тэмээний байрлах мѳр баганын дугаар. Мѳрийг дээрээс доош, баганыг зүүнээс баруун тийш $1$-ээс $n$ хүртэл дугаарлана.

Хэд хэдэн хариутай бол аль нэгийг нь хэвлэ.