Автобусні маршрути

У новому передмісті Миколаєва, що має форму прямокутника, усі дороги йдуть або строго з півдня на північ, або строго із заходу на схід. Таким чином, кожні дві дороги або паралельні одна до одної, або перпендикулярні й перетинаються в одному з перехресть. Усього в передмісті є $N$ горизонтальних доріг, $M$ вертикальних доріг та, відповідно, $N\cdot M$ перехресть.

Для передмістя саме зараз розробляють схему автобусних маршрутів. Усі маршрути повинні починатися у перехресті, що розташоване в лівому нижньому куті мапи, а закінчуватися у перехресті в її правому верхньому куті. До того ж між початковою та кінцевою точкою автобус повинен їхати за найкоротшим маршрутом, тобто завжди на північ або на схід (на будь-якому перехресті на своєму шляху, однак, автобус може змінити напрям свого руху з північного на східний чи навпаки). Деякі перехрестя можуть бути важливими: вони розташовані поблизу густонаселених районів, і через них неодмінно слід пропустити принаймні один автобусний маршрут.

Завдання

Ваша задача — спланувати мережу маршрутів таким чином, щоб через кожне важливе перехрестя проходив принаймні один маршрут, але загальна кількість маршрутів вийшла при цьому якомога меншою.

Вхідні дані

У першому рядку вхідного файлу містяться два натуральних числа: кількість горизонтальних доріг $N$ та кількість вертикальних доріг $M$ у передмісті. Відомо, що $2\le N\le M\le 1000$. У наступних $N$ рядках задано по $M$ перехресть: число $1$ означає, що відповідне перехрестя є важливим, а число $0$ — що дане перехрестя важливим не є..

Вихідні дані

Вихідний файл повинен містити єдине цiле число — невід’ємне ціле число — мінімальну кількість маршрутів, які можна пустити вздовж найкоротших шляхів із лівого нижнього перехрестя у праве верхнє, щоб ті покривали при цьому всі важливі перехрестя.

Приклади

Примітка

Один з маршрутів слід пустити по південній дорозі на схід, далі по східній дорозі на північ. Інший маршрут може проходити таким чином: спершу на північ до першого повороту, далі на схід, далі знову на північ і ще два перехрестя на схід.

Оцінювання

1. ($12$ балів): $N=2$

2. ($18$ балів): Кількість важливих перехресть не перевищує $3$

3. ($22$ балів): $M\le 60$

4. ($16$ балів): $M\le 250$

5. ($32$ бали): Без додаткових обмежень