Задачи очного тура личного первенства

На доске размером `N\ times\ M` разложено несколько монет разного номинала. В клетке может лежать не более одной монеты. Можно поставить шахматного коня на любую клетку доски, в том числе занятую монетой, и затем, делая ходы по шахматным правилам, собирать монеты на клетках. В конце путешествия конь должен вернуться на начальную клетку. За выполнение каждого хода нужно заплатить одну денежную единицу. Можно проходить по клеткам доски несколько раз и собрать не все монеты. Допустимо также круговое путешествие в 0 ходов, при котором конь не двигается с начальной клетки. Выигрыш в этой задаче определяется как разница между стоимостью собранных монет и количеством ходов, сделанных конем.

Напишите программу, вычисляющую максимальный выигрыш и последовательность ходов, которая позволит его получить.

Первая строка ввода содержит три целых числа – размеры доски `N` и `M` (`4\ ≤\ N,\ M\ ≤\ 100`) и количество монет `K` (`1\ ≤\ K\ ≤\ 15`). Далее следует `K` строк, содержащих по три целых числа – номера строки `r_i` (`1\ ≤\ r_i\ ≤\ N`) и столбца `c_i` (`1\ ≤\ c_i\ ≤\ M`) клетки, в которой находится `i`-я монета, и номинал монеты `a_i` (`1≤\ a_i\ ≤\ 100`).

В первой строке вывести одно целое число – максимальный выигрыш, во второй строке вывести последовательность номеров строк и столбцов клеток в порядке посещения их шахматным конем. Если существует несколько вариантов последовательности ходов с одинаковым выигрышем, то можно вывести любой из них.

8 8 4
2 6 10
4 8 2
6 5 15
7 5 2

19
4 6 3 4 2 6 3 8 5 7 6 5 4 6