Складывание тарелок
Компания Plate Shipping Company — это интернет-магазин, который, как следует из названия, специализируется исключительно на продаже тарелок. Они гордятся тем, что предлагают самый широкий ассортимент обеденных тарелок во вселенной от множества производителей.
Недавний анализ затрат показал, что компания тратит значительные средства на упаковку тарелок для отправки. Это частично связано с тем, что тарелки необходимо складывать в стопки перед помещением в контейнеры для отправки, и этот процесс занимает больше времени, чем ожидалось. Возможно, вы сможете помочь.
Тарелки для отправки поступают от нескольких производителей. Каждая партия тарелок от производителя приходит в виде стопки, упорядоченной по размеру (самая маленькая тарелка сверху, самая большая — снизу). Мы будем называть такую стопку правильно упорядоченной. Чтобы отправить все тарелки, необходимо объединить их в одну стопку, которая также должна быть правильно упорядоченной. Для объединения стопок производителей в одну разрешены два вида операций:
Разделение: стопку можно разделить на две, подняв любую верхнюю часть стопки и отложив её в сторону, чтобы сформировать новую стопку.
Объединение: две стопки можно объединить, поставив одну на другую. Это возможно только в том случае, если нижняя тарелка верхней стопки не больше верхней тарелки нижней стопки, то есть объединенная стопка должна быть правильно упорядоченной.
Обратите внимание, что часть любой стопки нельзя сразу поместить на другую стопку. Сначала её нужно разделить, а затем объединить с другой стопкой. Имея коллекцию стопок, вы должны найти минимальное количество операций, необходимых для их объединения в одну стопку. Следующий пример соответствует входным данным и показывает, как две стопки могут быть преобразованы в одну за пять операций:
Входные данные
Каждый тест начинается с строки, содержащей одно целое число n (1 ≤ n ≤ 50), которое обозначает количество стопок, которые необходимо объединить для отправки. Далее следуют n строк, каждая из которых описывает стопку. Эти строки начинаются с целого числа h (1 ≤ h ≤ 50), обозначающего высоту стопки. Это число сопровождается h положительными целыми числами, представляющими диаметры тарелок от верхней к нижней. Все диаметры не превышают 10000. Эти числа будут в неубывающем порядке.
Выходные данные
Для каждого теста выведите номер случая и минимальное количество операций (разделений и объединений), необходимых для объединения данных стопок в одну.