Шахівниця#13093

Шахівниця

1 секунда

256 мегабайтів

Дано таблицю з $n$ рядків і $m$ стовпців. У кожній клітинці записано $0$ або $1$ .

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

Далі за одну операцію можна змінити значення однієї клітинки з $0$ на $1$ або навпаки.

Потрібно отримати таблицю, у якій:

у верхній лівій клітинці записано $0$ ;
будь-які дві клітинки зі спільною стороною містять різні числа.

Знайдіть мінімальну кількість таких операцій за умови оптимального вибору рядка та стовпця для видалення.

Вхідні дані

У першому рядку задано два цілі числа $n$ та $m$ ( $2 \leq n, m \leq 2000$ 2 \leq n,m \leq 2000) — кількість рядків і стовпців таблиці.

У кожному з наступних $n$ рядків задано рядок довжини $m$ , який складається лише із символів $0$ та $1$ .

Вихідні дані

Виведіть одне ціле число — мінімальну кількість операцій зміни значень клітинок.

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

У першому прикладі після видалення другого рядка та другого стовпця залишиться таблиця з рядками 01 та 10. Змінювати значення клітинок не потрібно.

У другому прикладі можна видалити третій рядок і п'ятий стовпець. У таблиці, що залишиться, достатньо змінити значення клітинки в третьому рядку та першому стовпці з $1$ на $0$ . Без змін отримати потрібну таблицю неможливо.

У третьому прикладі після будь-якого вибору рядка та стовпця для видалення залишиться одна клітинка зі значенням $1$ . Її потрібно змінити на $0$ .

Оцінювання

$30$ балів — $n, m \leq 20$ n,m \leq 20.
$50$ балів — $min (n, m) \leq 20$ \min(n,m) \leq 20.
$120$ балів — без додаткових обмежень.