Masala E

Xotira 128 MB Vaqt 1000 ms

Minimal yig'indi

To'rtburchak $NxM$ jadval(har bir katakchada ma'lum bir son yozilgan) berilgan. O'yin boshida o'yinchi $(1,1)$ katakchada joylashgan. Bir harakatda unga qo'shni katakchaga o'ngga yoki pastga o'tishga ruxsat beriladi (chapga va yuqoriga o'tish ta'qiqlanadi). Katakchadan o'tayotganda o'yinchi ushbu katakchada yozilgan miqdorda pul to'laydi (u yo'lining birinchi va oxirgi kataklarida ham pul to'laydi). O'yinchi minimal qancha xarajat bilan $(N,M)$ katakchaga bora oladi.

Kiruvchi ma'lumotlar:

Birinchi qatorda $M,N$ butun sonlari $N,M(1≤M,N≤5*10^3)$ .

Keyingi $M$ ta qatorda har birida $N$ tadan son bo'lgan $A[]$ matritsa berilgan $A[i][j] (0<A[i][j]<10^5).$ .

Chiquvchi ma'lumotlar:

Yagona qatorda masala yechimini chop eting.

Misollar

#	input.txt	output.txt
1	6 5 4 4 3 5 4 1 2 1 5 5 4 4 4 4 5 4 6 1 1 2 4 4 5 6 4 1 1 2 3 1	21
2	3 10 3 1 2 3 1 2 3 2 3 2 3 2 3 3 1 1 1 1 3 1 2 3 2 1 1 3 1 1 1 1	17