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.

Giriş verilənləri

İ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.

Çıxış verilənləri

İ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.

Nümunələr