İş Elanları

Universitetinizdə tələbələr üçün iş yerləri mövcuddur və rəhbərlik tələbələri bu işlərə təyin etməkdə sizdən kömək istəyir. Məqsəd tələbələrin istədikləri mövqeləri seçmələrini təmin etmək və hər bir tələbəni bu mövqelərdən birinə təyin edərək maksimum məmnuniyyət əldə etməkdir.

Hər bir tələbə, istək sırasına görə dörd mövqe seçir. Birinci mövqe ən çox istənilən, növbəti mövqe isə birinci mövqe bu tələbə üçün mövcud olmadıqda növbəti ən çox istənilən mövqedir və s.

Tələbələrin təcrübəsi onların təhsil ilinə əsaslanır. Üçüncü kurs tələbələrinin seçimləri birinci kurs tələbələrinin seçimlərindən daha çox çəkiyə malik olmalıdır.

Rəhbərlik sizdən aşağıdakı məmnuniyyət matrisindən istifadə etməyinizi istəyir:

Sizin vəzifəniz tələbələri mövqelərə elə təyin etməkdir ki, yuxarıdakı matrisə əsasən bütün tələbələrin məmnuniyyətinin cəmi maksimum olsun. Hər bir tələbə bir mövqe almalıdır, lakin bütün mövqelər dolmaya bilər.

Giriş verilənləri

Girişdə bir neçə test halı olacaq. Hər bir test halı iki tam ədədlə başlayacaq, n (4 ≤ n ≤ 140) və m (1 ≤ m ≤ 70), burada n iş elanlarının sayını və m tələbələrin sayını göstərir. Növbəti n sətirin hər biri bir tam ədəd p (1 ≤ p ≤ 10) ehtiva edəcək, bu, həmin iş elanı üçün mövcud olan mövqelərin sayını göstərir. İş elanları iş 0-dan iş n-1-ə qədər sırayla verilmişdir.

İş elanlarından sonra tələbələri təsvir edən m sətir olacaq. Hər bir tələbə sətiri beş tam ədəd ehtiva edəcək:

y c_1 c_2 c_3 c_4

Burada y (y=1, 2 və ya 3) tələbənin təhsil ilini, c_1, c_2, c_3 və c_4 (0 ≤ c_1, c_2, c_3, c_4 < n, hamısı dörd fərqli) tələbənin iş elanları seçimlərini, istək sırasına görə göstərir.

Hər bir test halı üçün hər bir tələbənin seçim siyahısında olan mövqelərdən birini ala biləcəyi bir həllin mövcudluğu təmin edilir.

Giriş iki 0 ilə bitən bir sətirlə sona çatacaq.

Çıxış verilənləri

Hər bir test halı üçün maksimum məmnuniyyəti göstərən bir tam ədəd çıxış edin. Boşluq çıxarmayın və cavablar arasında boş sətir çıxarmayın.