| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
На новом мобильном телефоне фирмы Mokia установлена игра <<Bloxx city>>. Действие этой игры происходит на прямоугольном поле размером $n$ на $m$.
Каждая клетка этого поля может быть пустой или в ней может находиться дом некоторой высоты. За один ход игрок может в пустой клетке построить дом. При этом дом высоты $h$ в некоторой клетке можно строить только, если в клетках, имеющих с рассматриваемой общую сторону, находятся дома всех высот от 1 до $h-1$ (соответственно, дом высоты 1 можно строить в любой свободной клетке поля).
Изначально на поле уже стоят некоторые дома. Цель игры --- построить дополнительные дома так, чтобы их суммарная высота была как можно большей.
Напишите программу, которая позволяет добиться этой цели.
Первая строка входного файла содержит два целых числа: $m$ и $n$ (1ドル \le m, n \le 10,ドル $m \cdot n \le 16$). Последующие $m$ строк описывают игровое поле: каждая из них содержит по $n$ чисел $h_{i, j}$ (0ドル \le h_{i, j} \le 5$), задающих высоты домов, изначально стоящих на поле. Если некоторое из чисел $h_{i, j}$ равно нулю, то эта клетка пуста.
В первой строке выходного файла выведите максимальную возможную сумму высот домов. Во второй строке выходного файла выведите $k$ --- число ходов, которые необходимо сделать, чтобы добиться такой суммы высот. В последующих $k$ строках выведите описание этих ходов: каждая из них должна содержать по три числа: $r,ドル $c,ドル $h$ --- соответственно, координаты клетки, в которой строится дом, и его высоту (1ドル \le r \le m,ドル 1ドル \le c \le n$).
3 4 0 2 4 0 0 2 0 3 0 0 0 0
29 8 1 4 1 2 1 1 3 3 1 3 1 2 3 4 2 1 1 3 3 2 3 2 3 5