Dovşanlar və hamsterlər#430
Yemək axtarışında böyük, xoşbəxt bir dovşan ailəsi kök tarlasına gəlib çıxır. Təəssüf ki, onlardan bir az əvvəl, böyük, xoşbəxt və ac bir hamster ailəsi də ora çatır. Münaqişənin qarşısını almaq üçün qərara alınır ki, tarladan növbə ilə məhsul yığılacaq. Tarla sıradan ibarətdir, hər sırada kollar var; hər kolun üzərində müəyyən miqdarda kök var. Məhsul yığan şəxs ilk sıradakı istənilən koldan başlayıb son sıraya doğru hərəkət edir və aşağıdakı qaydaya görə koldan kola keçir: -ci sıranın -cı kolundan yalnız (l+1)-ci sıradakı k-1, və ya k+1 nömrəli kollara keçmək olar (əgər belə kollar mövcuddursa). Ziyarət edilən hər kol tamamilə köksüz edilir. Birinci dovşan məhsul yığır, sonra hamster, sonra yenə dovşan və s., tarlada ən azı bir kök qalana qədər bu cür davam edir.
Dovşanlar tələskəndir və ən əlverişli görünən yolu seçirlər: birinci sırada ən çox kökü olan koldan başlayırlar və hər addımda üç mümkün variantdan ən çox kökü olan kolu seçirlər (əgər bir neçə kolda eyni sayda kök varsa, ən böyük nömrəli olanı seçirlər). Hamsterlərsə, əvvəl gəldiklərindən tarlanın dəqiq xəritəsini çəkib və məhsul yığıldıqca onu yeniləyirlər, beləliklə, hər hamster özü üçün maksimum kök yığmağa imkan verən yolu seçir (əgər bir neçə yol eyni maksimum kök verirsə, ən böyük nömrəli koldan keçən yolu seçir).
Tarlanın xəritəsi verilib. Hər dovşan və hər hamster ayrı-ayrılıqda nə qədər kök yığa bilər?
Birinci sətirdə testlərin sayı verilir. Hər bir test iki tam ədədlə — və (1 \leq n, m \leq 100) başlayır. Sonra sətirdə, hər birində tam ədəd x_{i,j} (0 \leq x_{i,j} \leq 10) verilir. x_{i,j} — -ci sıranın -ci kolundakı köklərin sayıdır.
Hər test üçün ayrı sətirdə iki ədəd — dovşanların və hamsterlərin topladığı köklərin sayını çap edin.
Nümunə 1