Во градот на ритчиња и долини, на Факултетот за информатички науки, група студенти го развила најсофистицираниот хуманоиден робот – суперхерој, Финкимен.

Целта на Финкимен е да се справува со опасностите во градот. Финкимен сеуште е во развојна фаза, но се наближуваат избори - па градоначалникот сака да ја промовира новата одбрана во градот. Која мана ја има (засега) Финкимен? Тој може експресно да се движи на рамен терен и многу брзо да се движи по угорници (нагоре), но има големи проблеми и мноогу бавно се движи по удолници (надолу).

Сепак, бидејќи зборуваме за робот – суперхерој, имаме предност што може да се произведат повеќе роботи од истиот тип.

Заради конфигурацијата на градот, можно е навистина да има потреба од повеќе роботи за тие да може многу брзо да се справат со некаква опасност која е во тек (пожар, поплава, грабеж, ...).

Значи, даден ни е градот во вид на правоаголна шема, во која во секое поле е запишана висината на теренот во неа. Вие може да поставите роботи на кои било позиции, но барем еден од нив мора да може да стигне брзо од местото на кое што ќе го поставите до местото каде што ќе се појави опасност. Роботот може да се движи од едно поле до кое било соседно кое има заеднички раб со тоа поле (значи, хоризонтално и вертикално).

Бидејќи продукцијата на роботите е скапа, треба да се најде најмалиот број на роботи така што ќе се овозможи брза интервенција за првата појавена опасност.

Влез

Во првата линија се запишани два цели броеви R и C (1 <= R, C <= 50). Во секоја од следните R линии се наоѓаат по C цели броеви Mij (1 <= Mij <= 30), кои ја дефинираат конфигурацијата на теренот. Притоа, пониските места имаат помала вредност за Mij од повисоките места.

Излез

На стандарден излез отпечатете го бараниот најмал број на роботи.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
11 11
3 3 3 3 3 3 3 3 3 3 3
3 1 1 1 1 1 1 1 1 1 3
3 1 1 1 1 1 1 1 1 1 3
3 1 1 9 7 7 7 9 1 1 3
3 1 1 7 4 4 4 7 1 1 3
3 1 1 7 4 4 4 7 1 1 3
3 1 1 7 4 4 4 7 1 1 3
3 1 1 9 7 7 7 9 1 1 3
3 1 1 1 1 1 1 1 1 1 3
3 1 1 1 1 1 1 1 1 1 3
3 3 3 3 3 3 3 3 3 3 3

излез
2

влез
2 2
1 2
2 1

излез
2

Објаснување за првиот пример: 2 робота, еден на некоја од позициите со висина 1 и друг на некоја од позициите со висина 4. Така, ако се појави опасност во кое било поле, барем еден од нив ќе може да дојде до соодветното поле движејќи се по рамен пат и по угорница.

Објаснување за вториот пример: Потребни се 2 роботи (роботите можат да се движат само хоризонтално и вертикално - не можат дијагонално!).