Məsələlər
Bağa: bərpaetmə
Bağa: bərpaetmə
Bağa düzbucaqlı cədvəldə sol yuxarı küncdən sağ aşağı küncə marşurutla az itki ilə getmək istəyir.
\InputFile
İlk sətirdə cədvəlin ölçülərini ifadə edən iki natural $n$ və $m~(n, m \le 1000)$ ədədləri verilir. Növbəti $n$ sətrin hər birində boşluqla ayrılmış $m$ ədəd --- hər xanadakı kislotanın miqdarını (millimetrlə) ifadə edən ədədlər cədvəli verilir.
Bağa yalnız sağ və ya sol xanaya hərəkət edə bilər.
\OutputFile
İlk sətirdə bir tam ədəd bağa üçün mümkün minimal itkini ifadə edən bir tam ədəd çap edin. Növbəti sətirlərdə uyğun yolu göstərən xanaların koordinatlarını çap edin. Koordinatları onların yoldakı rast gəlindiyi ardıcıllıqda cap edin.
\includegraphics{https://static.e-olymp.com/content/5c/5cd94d974a6c5b3b8a5b52adcb72a55ca64ce967.gif}
Giriş verilənləri #1
3 4 5 9 4 3 3 1 6 9 8 6 8 12
Çıxış verilənləri #1
35 1 1 2 1 2 2 2 3 3 3 3 4
Giriş verilənləri #2
1 1 1
Çıxış verilənləri #2
1 1 1