Alternativ yollar#4637
Verilmiş düzbucaqlı cədvəl sətir və sütundan ibarətdir. Hər bir hüceyrədə -dən çox olmayan natural ədəd yerləşdirilib. Səyyah bu cədvəldə sol yuxarı küncdən sağ aşağı küncə qədər hər addımda ya hüceyrə sağa, ya da hüceyrə aşağı hərəkət edərək keçməlidir. Belə yolların sayı çoxdur. Hər bir yol üçün keçilən hüceyrələrdəki ədədlərin cəmini hesablamaq mümkündür. Bu cəmlər arasında maksimum olanı tapmaq mümkündür.
Səyyaha qarşı səxavətli olaq və yaxşı yolları yalnız dəqiq maksimum cəmi əldə edən yollar kimi deyil, həm də cəmi maksimumdan -dən çox fərqlənməyən yollar kimi qəbul edək. Yaxşı yolların sayı 10^9-dan çox olmayacağına zəmanət verilir.
Maksimum mümkün cəmi və yaxşı yolların sayını tapan proqram yazın.
Birinci sətir üç tam ədəd: (2 \leq M \leq 200), (2 \leq N \leq 200), (0 \leq K \leq 200) ehtiva edir. Növbəti sətirin hər biri uyğun hüceyrələrdə yazılmış ədəd ehtiva edir.
Birinci sətir maksimum mümkün cəmi, ikinci sətir isə cəmi maksimumdan -dən çox fərqlənməyən yolların sayını ehtiva etməlidir.
Nümunə 1