Demək olar ki, maksimum

Verilmiş düzbucaqlı cədvəl N sətir və M sütundan ibarətdir və hər bir hüceyrə 1000-dən çox olmayan natural ədədlərlə doldurulmuşdur. Sol üst küncdən sağ alt küncə yalnız sağa və ya aşağıya hərəkət edərək keçmək lazımdır. Bu zaman keçilən hüceyrələrdəki ədədlərin cəmini hesablayırıq. Məqsədimiz bu üsulla əldə edə biləcəyimiz maksimum cəmi tapmaqdır.

Lakin bu, hələ hamısı deyil. Əgər toplanmış ədədlərin cəmi maksimum cəmdən K qədər və ya daha az fərqlənirsə, bu yolu demək olar ki, maksimum adlandırırıq (0 <= K <= 100). Burada da sol üst küncdən sağ alt küncə yalnız sağa və ya aşağıya hərəkət edən yollar nəzərdə tutulur. Demək olar ki, maksimum yolların sayını müəyyən etmək tələb olunur. Onların sayı çox ola bilər, buna görə də demək olar ki, maksimum yolların sayının 20102010-a bölünməsindən qalanı tapmaq lazımdır.

Giriş məlumatları

Birinci sətirdə üç natural ədəd verilir: N (2 <= N <= 300), M (2 <= M <= 300) və K (0 <= K <= 100). Növbəti N sətirin hər biri M ədəddən ibarətdir, 1000-dən çox olmayan natural ədədlər – cədvəlin məzmunu. Sətirdəki qonşu ədədlər bir boşluqla ayrılır.

Çıxış məlumatları

Birinci sətirdə bir natural ədəd olmalıdır – sol üst küncdən sağ alt küncə qaydalara uyğun hərəkət edərək toplaya biləcəyiniz ən böyük cəm. İkinci (və son) sətirdə bir tam ədəd olmalıdır – demək olar ki, maksimum yolların sayının 20102010-a bölünməsindən qalan.