Задача . F2. Алиса и перекрашивание 2

Разница между версиями заключается в стоимости операций. Решение для одной версии не будет работать для другой!

У Алисы есть таблица размером \(n \times m\), изначально все ее клетки окрашены в белый цвет. Клетка на пересечении \(i\)-й строки и \(j\)-го столбца обозначается как \((i, j)\). Алиса может выполнять следующие операции:

• Выбрать любой подпрямоугольник, содержащий клетку \((1, 1)\), и инвертировать цвета всех его клеток. (Инвертировать означает изменить цвет клетки с белого на черный или с черного на белый).

  Эта операция стоит \(1\) монету.

• Выбрать любой подпрямоугольник, содержащий клетку \((n, 1)\), и инвертировать цвета всех его клеток.

  Эта операция стоит \(3\) монеты.

• Выбрать любой подпрямоугольник, содержащий клетку \((1, m)\), и инвертировать цвета всех его клеток.

  Эта операция стоит \(4\) монеты.

• Выбрать любой подпрямоугольник, содержащий клетку \((n, m)\), и инвертировать цвета всех его клеток.

  Эта операция стоит \(2\) монеты.

Напомним, что подпрямоугольник — это все клетки \((x, y)\) с \(x_1 \le x \le x_2\), \(y_1 \le y \le y_2\) для некоторых \(1 \le x_1 \le x_2 \le n\), \(1 \le y_1 \le y_2 \le m\).

Алиса хочет получить свою любимую раскраску с помощью этих операций. Какое наименьшее количество монет ей придется потратить? Можно показать, что всегда можно преобразовать исходную таблицу в любую другую.