BS-H4. Tog‘ yo‘li

Tog‘li hudud n × m kataklarga bo‘lingan, har katakning balandligi berilgan. Sayyoh chap yuqori katakdan o‘ng pastkisiga bormoqchi; bir qadamda qo‘shni katakka (yuqori, past, chap, o‘ng) o‘tadi. Qadamning qiyinligi — ikki katak balandliklari ayirmasining moduli. Yo‘lni shunday tanlangki, undagi eng qiyin qadam imkon qadar oson bo‘lsin. Shu qiyinlikni chiqaring.

Ruxsat etilgan eng katta qiyinlik D berilsa, «yetib bo‘ladimi?» degan savolga BFS javob beradi.

Kirish ma’lumotlari

Birinchi qatorda n va m, keyingi n qatorda m tadan balandlik.

Chiqish ma’lumotlari

Bitta son — eng qiyin qadamning eng kichik qiymati.

Cheklovlar

1 ≤ n, m; n · m ≤ 2·10⁴; 0 ≤ balandlik ≤ 10⁶.