E. Петяа болон хойлоонууд

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

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

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

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

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

Нийслэл Берланд нь 1-ээс $n$ хүртэл дугаарлагдсан $n$ ширхэг усны тараншантай. Эдгээр тараншанууд нь нэг чиглэлтэй хоолойнуудаар хоорондоо холбогдсон. Ямар ч хоёр хос тараншанууд нь хоорондоо чиглэл бүрд хамгийн ихдээ нэг хоолоогоор холбогдсон. Хоолой бүр нь эерэг бүхэл тоон өргөнтэй. Өргөн нь тухайн хоолооны нэг агшинд дамжуулж чадах усны литерийг тодорхойлдог. Ус хотруу усны гол тараншанаар (1 дүгээрх) дамжин орж ирдэг. Ус тодорхой хоолойгоор дамжин өнгөрөх ёстой ба цэвэрлэх системийн (n дүгээрх) гадагшлуулах тараншанд хүрнэ.

Петяа зарим хоолойнуудын өргөнийг хоолой бүрийн өргөн нь бүхэл тоогоор үлдэхээр нийтдээ $k$ нэгжээр нэмэгдүүлэхийг хүсэж байгаа. Энэ үйлдлийг хийсний дараа түүнд гол тараншанаас гадагшлуулах тараншан хүртэл нэгж хугацаанд дамжуулагдах усны хэмжээг тодорхойлоход тусал.

Оролт

Эхний мөр зайгаар тусгаарлагдсан хоёр бүхэл тоо $n, k (2 <= n <= 50, 0 <= k <= 1000)$-г агуулна. Дараагийн $n$ мөр бүр хоосон зайгаар тусгаарлагдсан $n$ бүхэл тоог агуулна. $i + 1$ дэх мөр, $j$ дэх багана нь $i$ дугаар тараншанаас $j$ дугаар тараншан хүрэх хоолойны өргөнийг заах $c_{ij} (0 <= c_{ij} <= 10^6, c_{ij} = 0)$ тоог агуулна. Хэрэв $c_{ij} = 0$ бол $i$ дахь тараншанаас $j$ дэх тараншан хүрэх хоолой байхгүй гэсэн үг.

Гаралт

Нэгж хугацаанд гол тараншанаас гадагшлуулах тараншан хүрэх хамгийн их усны хэмжээ болох ганц бүхэл тоог хэвлэнэ.

Орчуулсан: devman

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

Оролт
5 7
0 1 0 2 0
0 0 4 10 0
0 0 0 0 5
0 0 0 0 10
0 0 0 0 0
Гаралт
10
Оролт
5 10
0 1 0 0 0
0 0 2 0 0
0 0 0 3 0
0 0 0 0 4
100 0 0 0 0
Гаралт
5

Тэмдэглэл

Эхний тестэд Петяа 1-ээс 2-р тараншан хүрэх хоолойн өргөнийг 7-оор нэмэгдүүлж чадна.

Хоёр дугаар тест дээр Петяа 1-ээс 2-р тараншан хүрэх хоолойны өргөнийг 4-өөр, 2-оос 3-ынхыг 3-аар, 3-аас 4-ийнхийг 2-оор, 4-өөс 5-ынхыг 1-ээр тус тус нэмэгдүүлж чадна.

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