Задача B. Призыв в армию ≡

Условие

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

Рассмотрим как проходит призыв. Всего на учете в этом военкомате состоят n человек, а призвать необходимо m человек. На каждого стоящего на учете человека заведено личное дело, к которому прикреплена справка о его состоянии здоровья. Состояние здоровья человека характеризуется тремя параметрами: силой, ростом и весом. Правда некоторые люди предоставляют в военкомат «липовые» справки, в которых указаны ложные параметры состояния здоровья.

Военкомат может провести обследование и исправить данные в справке на истинные данные (то есть внести в личное дело истинное значение некоторого параметра здоровья, вместо указанного ранее). За определение каждого из параметров здоровья призывников отвечает отдельный врач. Таким образом, в результате одного обследования значение ровно одного параметра здоровья ровно одного призывника заменяется в его справке на истинное значение.

В силу ограниченности времени в военкомате не могут провести более k обследований призывников.

Задача подполковника: призвать m человек так, чтобы сумма параметров, указанных в справках всех призванных, была максимальна. Ваша задача — написать программу, которая решит проблему призыва в военкомате.

Формат входного файла

В первой строке входного файла записаны числа n, m, k. В следующих n строках указаны по 6 чисел. Первые три из них — сила, рост и вес в справке, следующие три — истинная сила, рост и вес.

Формат выходного файла

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

В каждой из последующих z строк выведите описание одного из обследований, которое требуется провести. Описание должно состоять из двух частей. Первая часть — номер призывника, которого необходимо обследовать. Вторая часть — это слово STRENGTH, если обследование должно быть направлено на выяснение его истинной силы, HEIGHT, если оно должно быть направлено на выявление его истинного роста, и WEIGHT, если оно должно быть направлено на выявление его истинного веса.

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

Призывники нумеруются натуральными числами от 1 до n в том порядке, в котором они заданы во входном файле.

Ограничения

Примеры тестов

3 2 4
1 1 1 1 1 1
1 1 2 2 2 3
7 12 44 0 0 0

70 3 
2 STRENGTH
2 HEIGHT
2 WEIGHT
2 3