В клубе коллекционеров монет состоят n
человек. В настоящее время клубом проводится конкурс – кто первым соберет полную коллекцию монет XIX века. По требованиям клуба, эта коллекция должна состоять из m
различных типов монет, причем, можно иметь больше одной монеты каждого типа, но обязательно хотя бы одну.
Вася решил подойти к этому вопросу основательно и хочет рассчитать оптимальную стратегию обмена монет. Он знает, что любой коллекционер с радостью обменяет любую свою монету a
на любую Васину монету b
, но только в одном случае: если у этого коллекционера больше одной монеты вида a
, но еще нет ни одной монеты серии b
. Ни на какие другие обмены коллекционеры не согласны. Сам Вася, в отличие от других, ставит глобальную оптимизацию выше локальной, и при желании может нарушать это правило.
Вася хочет с помощью таких обменов набрать как можно больше различных типов монет, чтобы облегчить себе в будущем задачу победы в конкурсе. Помогите ему рассчитать оптимальную стратегию обмена монетами!
В первой строке входного файла заданы два числа n
и m
(1 ≤ m
, n ≤ 100
). Далее следуют n
строк по m
чисел в каждой: j
-е число i
-й строки – это количество монет j
-го типа у i
-го коллекционера. Все эти числа неотрицательны и не больше 1000. Вася имеет номер 1.
В первой строке выходного файла выведите максимальное количество различных типов монет, которые можно собрать. Далее выведите любую из последовательностей обменов, приводящую к такому количеству различных типов. Каждый из обменов выводится в формате x[i]
, u[i]
, v[i]
, где x[i]
– номер коллекционера, с которым следует обменяться, u[i]
– номер монеты, которую Вася от него получает, а v[i]
– номер монеты, которую Вася ему отдает.