D. Каял ба Солигддог хавтгай

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

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

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

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

Фокс Каялд $n$ мөртэй, $n$ баганатай хавтгай байгаа ба нүд бүрт нэг бүхэл тоо байна.

Энд $n$ нь сондгой тоо гэдэг нь мэдэгдэж байгаа учир гэж тодорхойлно. Фокс Каял дараах үйлдлийг олон удаа хийж болно. Үүнд: Тэр $x$ мөртэй, $x$ баганатай дэд хавтгайг сонгох ба дараа нь бүх тоог -1-ээр үржүүлнэ.

Тэр эдгээр үйлдлүүдийг хийж тоонуудын хамгийн их нийлбэрийг буцаана.

Оролт

Энхий мөрөнд бүхэл $n$ ($1 ≤ n ≤ 33$, ба $n$ нь сондгой тоо) тоог оруулна. Энэ нь хавтгайн хэмжээ юмаа.

Дараагийн $n$ мөр бүрд $n$ ширхэг бүхэл тоонууд агуулагдана. Энэ нь хавтгайн элементүүд юм. Бүх элементүүдийн абсолют утга нь $1000$-аас хэтэрч болохгүй.

Гаралт

Нэг бүхэл тоо хэвлэнэ. Энэ нь бүх үйлдлийг гүйцэтгэсэний дараах хавтгайн тоонуудын хамгийн их нийлбэр юмаа.

Орчуулсан: Даариймаа

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

Оролт
3
-1 -1 1
-1 1 -1
1 -1 -1
Гаралт
9
Оролт
5
-2 0 0 0 -2
0 -2 0 -2 0
0 0 -2 0 0
0 -2 0 -2 0
-2 0 0 0 -2
Гаралт
18

Тэмдэглэл

Эхний жишээнд бид хоёр удаа үйлдлийг хийнэ. Үүнд: Зүүн дээд булангийн $2 × 2$ хэмжээтэй дэд хавтгайд, дараа нь баруун доод булангийн $2 × 2$ хэмжээтэй дэд хавтгайд тус тус хийнэ. Үүний дараа бүх тоо эерэг болсон байна.

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