Crazy Frog#405
Çoxunuz yəqin ki, Crazy Frog adlı kiçik qurbağanın macəraları haqqında mahnılar eşitmisiniz. Bu dəfə enerjili məxluq yemək yeməyə qərar verdi, amma hətta bu sadə işi oyun şəklində yerinə yetirdi. Beləliklə, N \times N (N \leq 50) ölçüsündə kvadrat oyun sahəsinin hər bir hüceyrəsində a_{ij} (təbii ədəd ) ağırlığında bir ağcaqanad var, burada – sıra nömrəsi, – sütun nömrəsidir. Qurbağa hüceyrədən hüceyrəyə tullanaraq ağcaqanadları yeyir. Oyunun qaydaları belədir: hər sütunda ən çox bir ağcaqanad yeyilə bilər. Hər dəfə bir ağcaqanad yeyildikdə, onun yeyildiyi sıra nömrəsi yadda saxlanılır və oyunun sonunda yeyilmiş ağcaqanadların sıra nömrələrinin cəmi məhz olmalıdır. Nəzərə alın ki, əgər bir sıra üzrə bir neçə ağcaqanad yeyilibsə, həmin sıra nömrəsi toplamada uyğun sayda nəzərə alınır.
Bu qaydalara əməl etməklə yeyilə biləcək maksimum ümumi ağcaqanad ağırlığını müəyyən edin.
Girişin ilk sətiri testlərin sayını ehtiva edir. Hər test üçün ilk sətrində ədədi verilir. Növbəti sətirin hər birində boşluqla ayrılmış ədəd a_{ij} verilir.
Hər test üçün çıxış faylında yeyilmiş ağcaqanadların ümumi ağırlığına bərabər bir ədəd çıxarılır.
Nümunə 1