Подарунок#12321

Подарунок

15 секунд

256 мегабайтів

Складна

На різдвяні свята вам подарували бінарну матрицю $A$ розміром $n \cdot m$ n \cdot m.

Ви можете робити наступні операції з нею:

Інвертувати значення всіх елементів рядка $i$ .
Інвертувати значення всіх елементів стовпця $j$ .

Матрицю називають гарною якщо виконується наступна умова для усіх значень $i$ та $j$ :

$A_{i, j} = A_{n - i + 1, m - j + 1}$ A_{i, j} = A_{n-i+1, m-j+1}

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

Вхідні дані

Перший рядок містить два цілих числа $n$ та $m$ $(1 \leq n, m \leq 5000)$ (1 \le n, m \le 5000) — розміри матриці $A$ . Наступні $n$ рядків містять по $m$ чисел $a_{i, j}$ a_{i,j} $(0 \leq a_{i, j} \leq 1)$ (0 \le a_{i,j} \le 1) — значення матриці $A$ .

Вихідні дані

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

Якщо відповіді не існує вивести $- 1$ .

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

До другого тесту:

Можемо зробити наступні перетворення:

$1010001101111010001101111$ \begin{smallmatrix} 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \end{smallmatrix} $\to$ $1010010010111010001101111$ \begin{smallmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \end{smallmatrix} інвертувавши 2 стовпець

$1010010010111010001101111$ \begin{smallmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \end{smallmatrix} $\to$ $1110011010101010101100111$ \begin{smallmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \end{smallmatrix} інвертувавши 2 рядок.

Для матриці $1110011010101010101100111$ \begin{smallmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \end{smallmatrix} виконується умова красоти. Можна довести що це найменша відповідь.

Оцінювання

Підзадача $1$ ( $20$ балів) : $(n, m \leq 10)$ (n, m \le 10)
Підзадача $2$ ( $15$ балів) : $(n = 1)$ (n = 1)
Підзадача $3$ ( $45$ балів) : $(n, m \leq 100)$ (n, m \le 100)
Підзадача $4$ ( $80$ балів) : $(n, m \leq 500)$ (n, m \le 500)
Підзадача $5$ ( $140$ балів) : Без додаткових обмежень