eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

У новому передмісті Миколаєва, що має форму прямокутника, усі дороги йдуть або строго з півдня на північ, або строго із заходу на схід. Таким чином, кожні дві дороги або паралельні одна до одної, або перпендикулярні й перетинаються в одному з перехресть. Усього в передмісті є 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

Пример

Входные данные #1
10 9
1 6
1 3
3
2 1
3
3
1 5
1 1
3
Выходные данные #1
1
2
2
3
Источник Джерело XXXI Всеукраїнська олімпіада з інформатики, Миколаїв, 2-6 квітня 2018