545. Доска с монетами

Вам дали размеченную доску, содержащую $N \times M$ клеток $-$ $N$ по строкам и $M$ по столбцам. На каждой клетке этой доски либо орлом, либо решкой вверх лежит монета. За одно действие можно взять две любые соседние по горизонтали или вертикали монеты и перевернуть их. В задаче требуется определить, за какое минимальное число действий можно так перевернуть монеты, что в результате орлы и решки будут лежать в шахматном порядке (т.е. чередоваться $-$ таких порядков ровно $2$), либо же сообщить, что это невозможно.

В первой строке записаны $2$ целых числа через пробел $-$ $N$ и $M$ ($1 \leq N \cdot M \leq 20$) $-$ размеры доски. Далее следуют $N$ строк, каждая из которых содержит по $M$ символов $-$ описание доски. Если очередной символ равен '0', то на этой клетке монета лежит вверх орлом, а если '1' $-$ то решкой.

Выведите ответ на задачу, либо же число $-1$, если решения нет.

В первом тесте одна из оптимальных последовательностей переворотов такая:

001
011

010
011

010
101