Хомякlar və dovşanlar
Böyük mehriban dovşan ailəsi yemək axtarışında yerkökü sahəsinə gəlib çatdı. Təəssüf ki, onlardan əvvəl böyük mehriban ac hamster ailəsi də buraya gəlmişdi. Münaqişədən qaçmaq üçün məhsulu növbə ilə yığmaq qərara alındı. Sahə n sıra və m koldan ibarətdir; hər kolda müəyyən miqdarda yerkökü yetişir. Növbəti yığıcı birinci sıranın istənilən kolundan başlayır və sonuncuya doğru hərəkət edir, bir koldan digərinə aşağıdakı qaydaya əsasən keçir: l sırasındakı k nömrəli koldan yalnız l + 1 sırasına k - 1, k, k + 1 nömrəli kollardan birinə keçmək olar (əlbəttə, əgər belə nömrəli kollar varsa). Hər ziyarət edilən kol tamamilə yerköküdən təmizlənir. Məhsul yığımına ilk olaraq dovşanlardan biri çıxır, sonra hamster gəlir, sonra yenə dovşan və beləliklə, sahədə ən azı bir yerkökü qaldığı müddətcə davam edir.
Dovşanlar tələsikdir, ona görə də onlar xaricdən ən sərfəli yolu seçirlər: birinci sıranın ən zəngin kolundan başlayırlar və üç növbəti variantdan həmişə ən böyük kolu seçirlər (bir neçə kol eyni sayda yerkökü ilə varsa, ən böyük nömrəli kol seçilir). Sahəyə əvvəl gələn hamsterlər sahənin ətraflı xəritəsini tərtib etməyə və məhsul yığımı haqqında operativ məlumatlar əsasında onu aktual vəziyyətdə saxlamağa müvəffəq oldular, ona görə də onlar hər hamster üçün mümkün olan maksimum yerkökü yığmağa imkan verən yolu seçirlər (maksimum mümkün yerkökü ilə bir neçə variant varsa, ən böyük nömrəli kol vasitəsilə yol seçilir).
Məlum sahə xəritəsinə görə, dovşanların və hamsterlərin ayrı-ayrılıqda nə qədər yerkökü yığa bildiyini müəyyən edin.
Giriş verilənləri
Birinci sətir testlərin sayını ehtiva edir. Hər test iki tam ədəd n və m (1 ≤ n, m ≤ 100) ilə başlayır. Sonra n sətir gəlir, hər birində m ədəd x_i_{,}_j (0 ≤ x_i_{,}_j ≤ 10) var. x_i_{,}_j - i-ci sıranın j-ci kolundakı yerkökü sayıdır.
Çıxış verilənləri
Hər test üçün ayrı sətirdə dovşanlar və hamsterlər tərəfindən yığılmış yerkökü sayını göstərən iki ədəd çıxarın.