Masala H
Labirintsimon graflar
Lochinbek maktab tomonidan uyushtirilgan musobaqada sayohat uchun vaucher yutib oldi va buni bitta sharti bor edi u sayohat davomida minimal miqdorda pul sarflashi kerak edi. U \(n*m\) o`lchamdagi shaharlarni \(1*1\)-sida turibdi har bir shaharga kirish uchun to`lovlar mavjud u 1-shaharga kirish uchun ham to`lov qilishi kerak. u \(m*n\)-shaharga minimal pul sarflab o`tishi kerak u faqat o'ngdagi yoki pastdagi shaharlarga o'tishi mumkin! Siz unga minimal miqdorda qancha pul sarflashi kerakligini aniqlab bering.
Birinchi qatorda \(n\) va \(m\) beriladi \(2<= n, m <= 1000\)
keyin sizga \(n*m\) o`lchamdagi matritsa beriladi bu matritsa shaharga kirish uchun qancha pul to`lash kerakligini bildiradi ya'ni narxlar matritsasi.
Eng kamida qancha pul sarflab \(n*m\)-shaharga yetib borish mumkinligini chop eting!
| # | input.txt | output.txt |
|---|---|---|
| 1 |
4 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 |
7 |
Telegram kanalimizga obuna bo'ling