Vilayət Region Yarışma Komanda Oyun#3788
ACM müsabiqəsi yalnız fərdi bacarıqlara deyil, həm də komanda işinə əsaslanır. Bir komanda bu iki elementi birləşdirərək üstünlük qazana bilər.
Bir məktəbdə N ACM müsabiqə namizədi var. Məşqçi bu N namizəddən K nəfəri seçib Hunan əyalətinin regional müsabiqəsinə göndərmək istəyir. Hər komandanın 3 üzvdən ibarət olduğunu və hər bir üzvün şəxsi bacarıqlarını təmsil edən A dəyərinə malik olduğunu fərz edirik. Hər bir üzv cütlüyü üçün, həmin cütlük üçün komanda iş bacarıqlarını göstərən W dəyəri mövcuddur. Əgər bir komandada a, b, c olmaqla 3 üzv varsa, bu komandanın ümumi bacarıqları aşağıdakı formula ilə hesablanır:
A[a]+A[b]+A[c]+W[a][b]+W[a][c]+W[b][c];
Əyalət regional müsabiqəsinin qaydalarına görə, komanda balı çox önəmlidir. Məşqçi K komanda quraraq ümumi komanda balının maksimum olmasını təmin etmək istəyir.
Müsabiqə namizədlərindən komanda üzvlərini ağıllı seçməklə K komandanın maksimum balını tapa bilərsinizmi?
Birinci sətirdə T (T ≤ 10) test halının sayı verilir. Hər bir test halı üçün birinci sətirdə iki ədəd K, N (1 ≤ K ≤ 6, 3*K ≤ N ≤ 18) var ki, bu da komandaların və namizədlərin sayını göstərir. İkinci sətirdə N ədəd A_1 ... A_n, (0 ≤ Ai ≤ 100000) var ki, bu da hər bir namizədin şəxsi bacarıqlarını təmsil edir. Növbəti N sətirdə hər sətirdə N ədəd var ki, bu da W_nn matrisidir. W_ij komanda üzvü i və j arasında komanda iş bacarığını təsvir edir, 0 ≤ W_{ij }≤ 100000 və W_ij=W_ji.
Hər bir hal üçün, K komanda üçün maksimum balı təmsil edən bir ədəd çıxış edin.
Nümunə 1