Sofa, Belə Yaxşı
So a'nın Divan Salonu, xüsusi divanların istehsalı və təchizatında ixtisaslaşmışdır. Onların istehsal prosesi uzun müddət sirr olaraq qalmışdı, lakin son zamanlarda məlum olub ki, divan istehsalı iki mərhələdən ibarətdir: çərçivə və döşəmə. Divan dəsti üçün sifariş daxil olduqda, idarəetmə qrupu hər bir işçinin divanı çərçivəyə salma sürətini nəzərə alaraq, hansı işçinin hansı divanı çərçivəyə salacağını müəyyən edir ki, çərçivə üçün sərf olunan ümumi vaxt minimuma endirilsin. İdarəetmə həmişə sifarişin yerinə yetirilməsi üçün kifayət qədər işçinin olmasını təmin edir və hər bir işçi sifariş başına yalnız bir divanı çərçivəyə sala bilər (təkrarlanan hərəkət zədəsi iddialarının qarşısını almaq üçün).
İşçilər çərçivə işinə başladıqdan sonra, idarəetmə hər bir işçinin divanı döşəmə vaxtını nəzərə alaraq döşəmə mərhələsini planlaşdırır. Onlar hər bir işçiyə çərçivəyə saldığı divandan fərqli bir divanı döşəmək üçün təyin etməlidirlər. İşçi, döşəmək üçün təyin edildiyi divanın başqa bir işçi tərəfindən çərçivəyə salınmasının bitməsini gözləməli ola bilər. Əgər işçilər çərçivə və döşəmə mərhələləri arasında boşdursa, adətən şirkətin əyləncə obyektində dincəlirlər, burada "tag" oynayırlar (bu otaq "chase lounge" adlanır). İdarəetmə onları bu oyunu oynamaqdan dayandırmağa çalışdı, lakin "Bu tagı çıxarmayın." yazısı ilə qarşılaşdı.
İşçilər işləsələr də, "tag" oynasalar da saat hesabı ilə ödəniş aldıqları üçün, idarəetmə işçilərin sahədə keçirdikləri ümumi saat sayını minimuma endirmək istəyir (əvvəlki çərçivə təyinatı və hər bir işçinin döşəmə işini bitirdikdən sonra dərhal ayrılması faktı nəzərə alınaraq). İdarəetmə belə bir problemi həll etməyə hazır deyil, ona görə də sizdən onlara kömək edəcək bir proqram təmin etməyinizi xahiş ediblər.
Giriş verilənləri
Hər bir test halı müsbət tam ədəd n ≤ 50 ilə başlayacaq, bu həm divanların, həm də işçilərin sayını göstərir (heç bir işçi kənarda qalmır). Növbəti n sətir hər biri n müsbət tam ədəd ehtiva edir; i-ci sətirdəki j-ci dəyər işçi j-nin divan i-ni çərçivəyə salma vaxtını göstərir (işçilər və divanlar 1-dən başlayaraq nömrələnir). Bundan sonra oxşar formatda döşəmə vaxtlarını təsvir edən n daha çox sətir gəlir. Verilən bütün vaxtlar 1000-dən çox olmayacaq. Tək 0 olan bir sətir girişi bitirəcək.
Çıxış verilənləri
Hər bir test halı üçün, işçi 1-dən başlayaraq hər bir işçi üçün bir sətir olmaqla, işçi tərəfindən çərçivəyə salınan divanı, döşədiyi divanı və döşəmə işini bitirdiyi vaxtı göstərərək, işçi 1-dən başlayaraq işçi nömrəsini və divan nömrəsini çıxış edin. Bütün işçilərin çərçivə işinə 0 vaxtında başladığını qəbul edin. Hər bir mərhələ üçün dəqiq bir optimal işçi və divan cütləşməsi olacaq. Bu sətirlərdən sonra həmin sifariş zamanı chase lounge-da işçilər tərəfindən sərf olunan ümumi boş vaxtı çıxış edin. Nümunədə göstərilən formatdan istifadə edin.