Торговці картинами#1527
Є спільнота поціновувачів мистецтва, які купують і продають один одному зображення. Кожен продаж зображення повинен відповідати таким правилам:
Ціна, за якою зображення продається, має бути не менша тієї ціни, за яку воно було куплене.
Жоден торговець не може купити те саме зображення більше одного разу.
На ринку з'явилося нове зображення, і торговець придбав його за . Після цього це зображення перепродається між існуючими поціновувачами мистецтва. Вам задано можливі ціни, за якими кожен торговець може купити зображення в іншого. Припускаючи, що всі угоди відбуваються відповідно до наведених вище правил, знайдіть максимальну можливу довжину послідовності перепродажів.
Після завершення всіх операцій виведіть кількість людей, які коли-небудь володіли зображенням, включаючи як останнього власника, так і торговця .
Вхід складається з кількох тестових випадків, кожен з яких має такий формат. У першому рядку міститься число торговців (2 \leq n \leq 15). Кожен з наступних рядків містить по цифр. Вони описують матрицю цін, де -й символ -го рядка — це ціна, за якою торговець купить зображення у торговця . Відомо, що — це найменша ціна, а — найбільша.
Для кожного тесту визначте максимальну можливу довжину послідовності перепродажу нового зображення та виведіть кількість людей, які коли-небудь володіли зображенням, включаючи останнього власника й торговця . Відповідь на кожен тест слід виводити в окремому рядку.
Приклад 1