Автобусні маршрути
У новому передмісті Миколаєва, що має форму прямокутника, усі дороги йдуть або строго з півдня на північ, або строго із заходу на схід. Таким чином, кожні дві дороги або паралельні одна до одної, або перпендикулярні й перетинаються в одному з перехресть. Усього в передмісті є N горизонтальних доріг, M вертикальних доріг та, відповідно, N*M перехресть.
Для передмістя саме зараз розробляють схему автобусних маршрутів. Усі маршрути повинні починатися у перехресті, що розташоване в лівому нижньому куті мапи, а закінчуватися у перехресті в її правому верхньому куті. До того ж між початковою та кінцевою точкою автобус повинен їхати за найкоротшим маршрутом, тобто завжди на північ або на схід (на будь-якому перехресті на своєму шляху, однак, автобус може змінити напрям свого руху з північного на східний чи навпаки). Деякі перехрестя можуть бути важливими: вони розташовані поблизу густонаселених районів, і через них неодмінно слід пропустити принаймні один автобусний маршрут.
####Завдання
Ваша задача — спланувати мережу маршрутів таким чином, щоб через кожне важливе перехрестя проходив принаймні один маршрут, але загальна кількість маршрутів вийшла при цьому якомога меншою.
Вхідні дані
У першому рядку вхідного файлу busways.in містяться два натуральних числа: кількість горизонтальних доріг N та кількість вертикальних доріг M у передмісті. Відомо, що 2 ≤ N ≤ M ≤ 1000. У наступних N рядках задано по M перехресть: число 1 означає, що відповідне перехрестя є важливим, а число 0 — що дане перехрестя важливим не є.
Вихідні дані
Вихідний файл busways.out повинен містити єдине цiле число — невід’ємне ціле число — мінімальну кількість маршрутів, які можна пустити вздовж найкоротших шляхів із лівого нижнього перехрестя у праве верхнє, щоб ті покривали при цьому всі важливі перехрестя.
####Оцінювання
Пiдзадача Бали Додатковi обмеження Необхідні підзадачі
0 0 Тести з умови -
1 12 N = 2 -
2 18 Кількість важливих перехресть не перевищує 3 -
3 22 M ≤ 60 -
4 16 M ≤ 250 0, 3
5 32 Без додаткових обмежень 0, 1, 2, 3, 4