Задача Коллекционирование монет

Описание

В клубе коллекционеров монет состоят 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 - номер монеты, которую Вася ему отдает.