Задача F. Марфа Геннадьевна на даче

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Марфа Геннадьевна собрала большой урожай лука и решила поделиться им с подружками. Она сделала N связок лука. В каждой связке K луковиц, причём луковицы расположены в одну линию, друг за другом.

Но к Марфе Геннадьевне пришли M подружек, где NK делится на M, но N не обязательно равно M. Чтобы никого не обидеть, Марфа Геннадьевна хочет разделить лук поровну между всеми подружками. Вероятно, для этого придётся разрезать некоторые связки.

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

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

Входной файл содержит целые числа N K M.

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

Выходной файл должен содержать целое число x — минимальное число разрезов.

Далее должны следовать N блоков чисел, по блоку на связку с луком. Для каждой связки нужно вывести информацию о разрезах. Каждый блок должен начинаться с целого числа ai — количества разрезов, за которым должны следовать (ai + 1) пар чисел bij cij (bij > 0, 1 ≤ cij ≤ M). Здесь bij — количество луковиц в j-й части связки, cij — номер подружки, которой достанется эта часть.

Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N, K, M ≤ 100.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 2 2
0
0  2 1
0  2 2
2
3 2 2
1
1  1 1  1 2
0  2 1
0  2 2

Разбор

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

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


0.085s 0.011s 15