B. Эмматай хамт оройн хоолонд

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

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

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

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

Жэк Эммаг гадуур оройн хоолонд урихаар шийдсэн. Жэк бол даруухан оюутан, тэр үнэтэй ресторанд орохыг хүсэхгүй байгаа. Эмма бол өндөр мэдрэмжтэй охин учир элит газруудыг илүүд үзнэ. Jack decides to invite Emma out for a dinner. Jack is a modest student, he doesn't want to go to an expensive restaurant. Emma is a girl with high taste, she prefers elite places.

Манхэтн $n$ гудамж болон $m$ өргөн чөлөөгөөс бүрдэнэ. Гудамж болон өргөн чөлөө бүрийн огтлолцол дээр нэг ресторан байдаг. Гудамжууд $1$-ээс $n$ хүртэл дугаарлагдсан ба өргөн чөлөөнүүд $1$-ээс $m$ хүртэл дугаарлагдсан. $i$-р гудамж $j$-р өргөн чөлөөний огтлолцол дээрх ресторанд хоол идэх өртөг нь $c_{ij}$.

Жэк Эмма хоёр ресторан сонгохдоо дараах байдлаар сонгоно. Эхлээд Эмма гудамжаа сонгох ба дараа нь Жэк өргөн чөлөөгөө сонгоно. Эмма Жэк хоёр сонголтоо хийхдээ Эмма оройн хоолыг хамгийн үнэтэй байлгахыг хүсэх бол Жэк хамгийн хямд байлгахыг хүснэ. Жэкийн хамгийн бага үнэтэй оройн хоолыг Эмма зөвшөөрнө. Хосыг хайранд умбуулах оройн хоолын өртгийг ол.

Оролт

Эхний мөрөнд хоёр бүхэл тоон утга $n, m$ ($1 ≤ n, m ≤ 100$) байх ба эдгээр нь Манхэтн дахь гудамжууд болон өргөн чөлөөнүүдийн тоо юм.

Дараагийн $n$ мөр бүр $m$ тооны $c_{ij}$ ($1 ≤ c_{ij} ≤ 10^{9}$)бүхэл тоон утгыг агуулах ба эдгээр нь $i$-р гудамж болон $j$-р өргөн чөлөөний оглолцол дээрх рестораны оройн хоолны өртөг юм.

Гаралт

Жэк Эмма хоёрын оройн хоолны өртөг болох ганц бүхэл тоон утга болох $a$-г хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
3 4
4 1 3 5
2 2 2 2
5 4 5 1
Гаралт
2
Оролт
3 3
1 2 3
2 3 1
3 1 2
Гаралт
1

Тэмдэглэл

Эхний жишээн дээр хэрвээ Эмма эхний эсвэл гурав дахь гудамжыг сонговол Жэк $1$ долларын өртөгтэй өргөн чөлөөг сонгож чадна. Тэгэхээр Эмма хоёр дахь гудамжийг сонгох ба Жэк дурын өргөн чөлөөгөө сонгоно. Оройн хоолны өртөг $2$ болно.

Хоёр дахь жишээн дээр Эммагийн сонголтоос үл хамааран Жэк $1$ өртөгтэй рестораныг сонгож чадна.

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