Mərc Dəstləri#4221
Yerli kazinonuz (Kaliforniyada müəyyən bir məsafədə yerləşir) yeni bir mərc oyununu sınaqdan keçirməyə qərar verib. Oyunçuya N sətir və M sütun olan bir kart üzərində cədvəl təqdim edilir. Cədvəlin hər bir i j girişi, baş gəlmə ehtimalı p_ij olan bir sikkə atışına uyğundur. Bütün sikkə atışları bir-birindən müstəqildir. Oyunçu hər sütundan dəqiq bir giriş olmaqla, hər biri M girişdən ibarət N dəst seçməlidir və hər bir giriş dəqiq bir dəfə istifadə olunmalıdır. Seçilmiş hər bir dəstdə bütün M sikkələr baş gələndə oyunçu 1 dollar qazanır. Kazino qeyri-adi dərəcədə səxavətli davranır və bu yeni oyunun tanıtımı çərçivəsində hər bir müştəriyə bir kart hədiyyə edir. İtiriləcək heç nəyiniz olmadığı üçün bu oyunu sınayacaqsınız. Bu kartdan gözlənilən qazancınızı necə maksimuma çatdıra bilərsiniz?
Giriş bir neçə test halından ibarətdir. Hər bir test halı, boşluqla ayrılmış iki tam ədəd N və M, 1 ≤ N ≤ 100, 1 ≤ M ≤ 10 olan bir sətirlə başlayır. Bu, cədvəlin p_ij girişlərini göstərən N sətir və M boşluqla ayrılmış rəqəmlərlə davam edir. Giriş N = M =0 olan bir sətirlə bitir, bu işlənməməlidir.
Hər bir test halı üçün verilmiş cədvəldən maksimum gözlənilən qazancı 4 ondalık dəqiqliklə çap edin.
Nümunə 1