Sofa, So Good
So a's Sofa спеціалізується на створенні та постачанні унікальних диванів. Їхній виробничий процес складається з двох етапів: каркасування та оббивка. Коли надходить замовлення на дивани, керівництво визначає, який працівник буде каркасувати який диван, щоб мінімізувати загальний час, витрачений на каркасування. Кількість працівників завжди дорівнює кількості диванів у замовленні, і кожен працівник може каркасувати лише один диван (через скарги на травми від повторюваних рухів).
Після початку каркасування керівництво планує фазу оббивки, знаючи, скільки часу кожному працівнику потрібно для оббивки кожного дивана. Кожен працівник отримує завдання оббити один диван (можливо, інший, ніж той, який він каркасував) після завершення каркасування. Працівники можуть чекати, поки диван, який їм призначено для оббивки, буде готовий. Якщо між етапами каркасування та оббивки вони бездіяльні, вони відпочивають у кімнаті відпочинку компанії, де грають у доганялки. Керівництво намагалося заборонити цю гру, але їх зупинив знак з написом "Не знімати цю бірку."
Оскільки працівникам платять погодинно, керівництво хоче призначити дивани для оббивки так, щоб мінімізувати загальний час перебування працівників на роботі (враховуючи раніше визначене призначення каркасування та те, що кожен працівник залишає роботу, як тільки закінчує оббивку). Керівництво звернулося до вас з проханням розробити програму, яка допоможе їм у цьому.
Вхідні дані
Кожен тестовий випадок починається з додатного цілого числа n ≤ 50, що вказує на кількість диванів та працівників. Наступні n рядків містять по n додатних цілих чисел; i-те значення в j-му рядку вказує час, який займає у працівника j каркасування дивана i (нумерація працівників і диванів починається з 1). Далі йдуть ще n рядків, кожен з яких містить n додатних цілих чисел, що описують часи оббивки в аналогічному форматі. Всі вказані часи не перевищують 1000. Рядок, що містить одне число 0, завершує введення.
Вихідні дані
Для кожного тестового випадку виведіть номер випадку, а потім n рядків, по одному на кожного працівника (починаючи з працівника 1). Для кожного працівника вкажіть диван, який він каркасував, диван, який він оббивав, і час, коли він закінчив свою роботу з оббивки, припускаючи, що всі працівники починають каркасування в момент часу 0. Існуватиме рівно одне оптимальне поєднання працівників і диванів для кожної фази. Після цих рядків виведіть загальний час бездіяльності, проведений працівниками в chase lounge під час цього замовлення. Використовуйте формат, показаний у прикладі.