N × M хэмжээтэй grid өгөгдөнө. Grid-ийн нүд бүр бүхэл тоон утгатай ба зарим нүд хаалттай (тэр нүдэнд очих боломжгүй).

Та (1,1) нүднээс эхлэн (N,M) нүд хүртэл очих ёстой.

Та дараах хөдөлгөөнүүдийг хийж болно:

• Баруун: (i, j) → (i, j+1)
• Доош: (i, j) → (i+1, j)
• Special move: (i, j) → (i+2, j+2)

Special move-ийг хамгийн ихдээ K удаа ашиглаж болно.

Special move хийх үед дундах нүднүүдийг алгасах ба зөвхөн очих нүд хүчинтэй байх ёстой.

Таны зорилго бол (1,1)-ээс (N,M) хүртэлх замаар явж, авсан онооны нийлбэрийг хамгийн их болгох юм.

Хэрэв (N,M) хүрэх боломжгүй бол -1 хэвлэнэ.

Оролт:

N M K
a11 a12 a13 ... a1M
a21 a22 a23 ... a2M
...
aN1 aN2 aN3 ... aNM

N, M — grid-ийн хэмжээ

K — special move-ийн дээд тоо

a[i][j]:

• integer (-10⁹ ≤ a[i][j] ≤ 10⁹)
• эсвэл # тэмдэг → хаалттай нүд

Гаралт:

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

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

• 1 ≤ N, M ≤ 1000
• 0 ≤ K ≤ 100
• \(-10^{18} ≤ a[i][j] ≤ 10^{18}\)

Дэд бодлого

Жишээ:

Оролт-1

3 3 1
1 2 3
4 5 6
7 8 9

Гаралт-1

15

Тайлбар-1

Хамгийн сайн зам: (1,1) → (1,2) → (2,2) → (3,3)

Оноо: 1 + 2 + 5 + 9 = 17

Гэхдээ special move ашиглавал:

(1,1) → (3,3)

Оноо: 1 + 9 = 10

? Иймээс энгийн зам илүү ашигтай → 17

⚠️ Гэхдээ зөвхөн баруун/доош явбал: (1,1) → (1,2) → (1,3) → (2,3) → (3,3) = 1+2+3+6+9 = 21

? Эцсийн зөв хариу: 21

Оролт-2

4 4 1
1 2 3 4
5 # 6 7
8 9 10 11
12 13 14 15

Гаралт-2

34

Тайлбар-2

Хаалттай нүд: (2,2)

Энгийн замууд зарим нь хаагдана.

Special move ашиглавал: (1,1) → (3,3) → (3,4) → (4,4)

Оноо: 1 + 10 + 11 + 15 = 37

Эсвэл: (1,1) → (1,2) → (2,3) → (3,4) → (4,4)

Оноо: 1 + 2 + 6 + 11 + 15 = 35

? Хамгийн сайн нь: 37