Вам задана матрица из \(n\) строк (пронумерованных от \(1\) до \(n\)) и \(m\) столбцов (пронумерованных от \(1\) до \(m\)). Обозначим за \(a_{i, j}\) число в клетке на пересечении \(i\)-й строки и \(j\)-го столбца, каждое число либо \(0\), либо \(1\).
Изначально в ячейке \((1, 1)\) находится фишка, которая будет перемещена в ячейку \((n, m)\) при помощи последовательности шагов. На каждом шаге фишка перемещается либо в ячейку справа от текущей, либо в ячейку снизу (если фишка сейчас в ячейке \((x, y)\), ее можно переместить либо в \((x + 1, y)\), либо в \((x, y + 1)\)). Фишка не может покидать матрицу.
Рассмотрим все пути фишки из ячейки \((1, 1)\) в ячейку \((n, m)\). Назовем путь палиндромным, если число в первой ячейке пути равно числу в последней ячейке пути, число во второй ячейке равно числу в предпоследней ячейке, и так далее.
Ваша цель — заменить минимальное количество элементов матрицы так, чтобы все пути стали палиндромными.