Masala #0178

Xotira 32 MB Vaqt 1000 ms

Matritsaning maksimal yig'indisi

Sizga 2N×2N o’lchamli matritsa berilgan. Siz 0 yoki bir necha marotaba matritsaning ixtiyoriy qatori yoki ixtiyoriy ustunini tanlab teskarisiga o’girishingiz mumkin. Shundan so’ng siz matritsaning yuqori chap burchagidagi N×N qism matritsaning yig’indisini hisoblaganingizda maksimal necha qiymatga ega bo’lishingiz mumkinligini aniqlang.

Masalan:

1	2	→	1	2	→	4	2
3	4	→	4	3	→	1	3

Kiruvchi ma'lumotlar:

Dastlabki satrda bitta butun son, N(1 ≤ N ≤ 500), keyingi 2N qatorning har birida bo’sh joy bilan ajratilgan holda 2N ta [0, 10⁶] oralig’idagi sonlar kiritiladi.

Chiquvchi ma'lumotlar:

Ixtiyoriy marotaba matritsaning ixtiyoriy qatori yoki ixtiyoriy ustunini teskarisiga aylantirishdan so’ng yuqori chap N×N qism matrisada maksimal yig’indi necha bo’lishini aniqlang.

Misollar

#	input.txt	output.txt
1	1 1 2 3 4	4
2	2 112 42 83 119 56 125 56 49 15 78 101 43 62 98 114 108	414