eolymp
bolt
Try our new interface for solving problems

Tor

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Siz m * n ölçülü torun yuxarı sol küncündəsiniz. Torun hər bir xanasında bir rəqəm var. k rəqəmi olan xanadan istənilən dörd istiqamətdə (üfiqi və şaquli) k xana atlaya bilərsiniz. Yuxarı sol küncdən aşağı sağ küncə minimal sayda nə qədər gediş etmək olar?

Giriş verilənləri

İlk sətirdə iki natural mn (1m, n500) ədədləri verilir. m və ya n ədədlərindən heç olmazsa birinin 1-dən böyük olmasına zəmanət verilir. Növbəti hər bir m sətir m * n torunu ifadə edən n rəqəm ehtiva edir. Hər bir rəqəm 0-dan 9-a qədər intervaldadır.

Çıxış verilənlər

Yuxarı sol küncdən aşağı sağ küncə gedişlərin minimal sayını verin. Əgər aşağı sağ küncə gəlmək mümkün deyilsə, IMPOSSIBLE verin.

Nümunə

Giriş verilənləri #1
2 2
11
11
Çıxış verilənləri #1
2
Giriş verilənləri #2
2 2
22
22
Çıxış verilənləri #2
IMPOSSIBLE
Mənbə 2015 ACM North America - Pacific Northwest, Дивизион 2, Задача O