Олонлог эгзэ сургуулийн "Их фестиваль" болж байна. Сургуулийн талбайг NxM хэмжээтэй тор (матриц) хэлбэрээр хуваажээ.

• Мөр → өдөр
• Багана → анги

Талбайн i-р мөр, j-р багана дээр:

• тухайн өдөр тухайн ангийн авсан оноо байрлана

Та фестивалийн хамгийн амжилттай хэсгийг олохыг хүсэж байна.

• Та ямар ч тэгш өнцөгт хэсгийг сонгож болно
• Сонгосон хэсэг:
  • дор хаяж 1 нүдтэй
  • мөр, баганаар дараалсан байх ёстой
  • Сонгосон тэгш өнцөгтийн талбай (cell тоо) нь K -аас бага байх ёстой. өөрөөр хэлбэл: (өндөр × өргөн) ≤ K

Таны зорилго

• Талбай ≤ K нөхцөлийг хангах
• хамгийн их нийлбэртэй дэд матрицын нийлбэрийг ол

Оролт:

Эхний мөрөнд 3 бүхэл тоо өгөгдөнө:

N M K

Дараагийн N мөрөнд M ширхэг бүхэл тоо:

a11 a12 ... a1M
a21 a22 ... a2M
...
aN1 aN2 ... aNM

Гаралт:

хамгийн их боломжит нийлбэр

Хязгаарлалтууд:

• \(1 ≤ N, M ≤ 200\)
• \(1 ≤ K ≤ N × M\)
• \(-10^3 ≤ a[i][j] ≤ 10^3\)

Дэд бодлого

Жишээ:

Оролт-1

2 2 4
1 -2
3 4

Гаралт-1

7

Тайлбар

Бүх матрицын талбай = 4 ≤ K

• Сонгож болно:

3 4

• Нийлбэр = 7

Оролт-1

2 3 2
1 -2 3
-1 4 -5

Гаралт-1

4

Тайлбар

K = 2 тул хамгийн ихдээ 2 нүд сонгоно

Боломжит:

[4] → 4 [3] → 3 [1 + (-2)] → -1

• Хамгийн их = 4