B. Дасгал хийв

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

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

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

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

Зун цаг ирж байна. Энэ нь Яхаб болон Яхабина хоёрын дасгал хийдэг үе ба тэд хоёулаа халуунд далайн эрэг харахыг хүсэж байгаа юм. Тэд зааланд $n$ мөртэй, $m$ баганатай $a$ матрицаар явна. $a[i][j]$ тоог заалны $i$-р мөр $j$-р баганын хэсэгт дасгал хийж шатаасан илчлэгийн хэмжээ гэж үзье.

Яхаб $1$-р мөр $1$-р багананд байрлаж дасгалаа хийж эхлээд $a[n][m]$ дасгалаар дуусгах хэрэгтэй. $a[i][j]$ дасгалыг дууссаны дараа тэр $a[i + 1][j]$ эсвэл $a[i][j + 1]$ дасгалруу явж чадна. Үүнтэй адил Яхабина ч бас $a[n][1]$ дасгалаас эхэлж $a[1][m]$ дасгалаар дуусгах хэрэгтэй. $a[i][j]$ хэсгийн дасгалыг хийсний дараа $a[i][j + 1]$ эсвэл $a[i - 1][j]$ хоёрын аль нэг рүү явж чадна.

Тэдний сургалтанд нэмэлт нэг нөхцөл байгаа. Тэд заалны яг нэг хэсэгт уулзана. Энэ хэсэгт тэдний аль нь ч дасгалгүй, хурдан зэрэг дэвшүүлэлтийн талаар (нэлээн хачин бяцхан яриа) ярилцах ба хоёулаа дараагийн дасгалдаа шилжинэ.

Хэрвээ Яхаб, Яхабина хоёрын аль нэг нь дасгалаа хийж дууссан бол энэ нь нийт ашиг гэж тооцогдоно. Нийт ашиг нь аль болох их байхаар тэр хоёрын дасгалыг төлөвлөнө үү. Яхаб, Яхабина хоёр өөр өөр хурдаар дасгалыг гүйцэтгэж чадна, тиймээс тэдний уулзах хэсгийн дугаар нь өөр өөр байх магадлалтай.

Оролт

Оролтын эхний мөр нь $n$, $m$ ($3 ≤ n, m ≤ 1000$) бүхэл тоонуудыг агуулна. Дараагийн $n$ мөр бүр нь $m$ бүхэл тоонууд агуулна: $i$-р мөрийн $j$-р тоо нь $a[i][j]$ ($0 ≤ a[i][j] ≤ 10^{5}$) элементийг илэрхийлнэ.

Гаралт

Гаралт нь нэг бүхэл тоо агуулна. Боломжит хамгийн их нийт ашиг.

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

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

Оролт
3 3
100 100 100
100 1 100
100 100 100
Гаралт
800

Тэмдэглэл

Яхабын сонгох дасгалууд $a[1][1] -> a[1][2] -> a[2][2] -> a[3][2] -> a[3][3]$. Яхабинагийн сонгох дасгалууд $a[3][1] -> a[2][1] -> a[2][2] -> a[2][3] -> a[1][3]$.

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