Складання Тарілок
Компанія Plate Shipping Company — це інтернет-ритейлер, що спеціалізується виключно на продажу тарілок. Вони пишаються тим, що пропонують найширший вибір обідніх тарілок у всесвіті від численних виробників.
У нещодавньому аналізі витрат компанія виявила, що витрачає значні кошти на пакування тарілок для відправки. Частково це пов'язано з тим, що тарілки потрібно складати перед тим, як помістити їх у контейнери для відправки. Це займає більше часу, ніж очікувалося. Можливо, ви можете допомогти.
Відправка тарілок складається з тарілок від кількох виробників. Тарілки від кожного виробника приходять складеними, тобто кожна розташована в одному ряду з тарілками, впорядкованими за розміром (найменша зверху, найбільша знизу). Ми будемо називати такий рядок правильно впорядкованим. Щоб відправити всі ці тарілки, ви повинні об'єднати їх в один рядок, знову правильно впорядкований. Щоб об'єднати ряди виробників в один рядок, дозволено два види операцій:
Розділити: один рядок можна розділити на два ряди, піднявши будь-яку верхню частину ряду і відставивши її вбік, щоб утворити новий рядок.
Об'єднати: два ряди можна об'єднати, поставивши один на інший. Це дозволено лише в тому випадку, якщо нижня тарілка верхнього ряду не більша за верхню тарілку нижнього ряду, тобто об'єднаний рядок має бути правильно впорядкованим.
Зверніть увагу, що частина будь-якого ряду ніколи не може бути безпосередньо поставлена на інший рядок. Спочатку її потрібно розділити, а потім розділену частину потрібно об'єднати з іншим рядком. Дано колекцію рядів, ви повинні знайти мінімальну кількість операцій, які перетворять їх в один рядок. Наступний приклад відповідає вхідним даним зразка і показує, як два ряди можуть бути перетворені в один рядок за п'ять операцій:
Вхідні дані
Кожен тестовий випадок починається з рядка, що містить одне ціле число n (1 ≤ n ≤ 50), кількість рядів, які потрібно об'єднати для відправки. Далі йде n рядків, кожен з яких описує рядок. Ці рядки починаються з цілого числа h (1 ≤ h ≤ 50), висоти ряду. Це число супроводжується h додатними цілими числами, які вказують діаметри тарілок, зверху вниз. Усі діаметри не перевищують 10000. Ці числа будуть у невисхідному порядку.
Вихідні дані
Для кожного тестового випадку виведіть номер випадку та мінімальну кількість операцій (розділень та об'єднань), які потрібно виконати, щоб об'єднати дані ряди в один рядок.