Pizza istəyirəm və mümkün qədər çox...#1299
Mikelancelo, bütün ninja tısbaqa qardaşları kimi, pizzanı çox sevirdi. Buna görə də, pizzeriyadan pizza yığmağa başlaya biləcəyi anı səbirsizliklə gözləyirdi. Lakin bu gün bir neçə problemlər gətirdi, əsas etibarilə pizzayolodan tısbaağanın çox pizza götürməsindən heç xoşu gəlmirdi...
Pizzayolonun gələcəkdə də pizza hazırlaya bilməsi üçün və ona minimum problem yaratmaq, eyni zamanda özü onu çox qəzəbləndirməmək üçün (yəni, tısbaağa artıq pizza yığılmış bir pizzeriya hüceyrəsindən ikinci dəfə keçməməlidir), Mikelancelo pizza yığmağa həmişə pizzeriyanın yuxarı sol küncündən başlayır və yalnız sağa və aşağı hərəkət edərək aşağı sağ qutusuna çatır. Sonra isə yalnız sola və yuxarı hərəkət edərək başlanğıc nöqtəsinə qayıdır.
Mikelanceloya ən çox sevdiyi yeməkdən mümkün qədər çox toplamağa imkan verəcək bir marşrut tapmasına kömək edin.
Giriş məlumatlarında bir neçə test halı var. Hər bir test halı pizzeriyadakı pizza qutularının sayı (1 < N \leq 600) olan sətrə başlayır. Sonrakı sətrin hər birində həmin mövqedə yerləşən pizza qutusundan tısbaağanın toplaya biləcəyi pizza diliminin sayı verilir. Bilinir ki, hər bir pizza qutusunda -dən çox pizza dilimlər ola bilməz.
Hər bir test halı üçün, Mikelancelonun toplaya biləcəyi optimal pizza dilimlərinin sayını çap edin.
Nümunə 1