Üzüm qurusu
Məşhur Plovdiv şokoladçısı Boni kişmişli şokolad plitəsini kəsmək istəyir. Plitə düzbucaqlı formadadır və vahid kvadrat parçalardan ibarətdir. Parçalar plitənin kənarlarına paralel şəkildə düzülüb və N sıra və M sütun təşkil edir, ümumilikdə NxM parça olur. Hər bir parçada bir və ya daha çox kişmiş var və kişmişlər parçaların arasında yerləşmir və ya kəsikləri keçmir.
Əvvəlcə şokolad plitəsi bütöv bir parçadır. Boni onu daha kiçik hissələrə kəsmək istəyir, nəhayət, bütün plitəni NxM tək parçalara ayırana qədər. Boni çox məşğuldur, buna görə də köməkçisi Petri şokolad plitəsini kəsməyə kömək etməsini xahiş etdi. Pet yalnız kənardan kənara düz kəsiklər edir. O, etdiyi hər kəsik üçün ödəniş almaq istəyir. Boninin heç pulu yoxdur, amma sonsuz miqdarda kişmişi var və Petri kişmişlə ödəmək niyyətindədir. Pet buna razıdır, amma belə bir şərtlə: hər dəfə şokoladın bir hissəsini iki kiçik hissəyə kəsəndə, o, həmin hissədə olan qədər kişmiş alır.
Boni Petriyə mümkün qədər az ödəmək istəyir. O, NxM parçaların hər birində nə qədər kişmiş olduğunu bilir. O, Petriyə hansı hissələri vermək üçün sıranı seçə bilər və həmçinin Petriyə hansı kəsikləri (üfüqi və ya şaquli) və harada etməli olduğunu deyə bilər. Boniyə şokolad plitəsini tək parçalara kəsməkdə və Petriyə mümkün qədər az kişmişlə ödəməkdə kömək edin.
Tapşırıq
Hər bir tək parçada olan kişmişlərin sayına görə, Boninin Petriyə ödəməli olduğu minimal kişmiş sayını müəyyən edən bir proqram yazın.
Giriş verilənləri
Proqramınız standart giriş axınından aşağıdakı məlumatları oxumalıdır:
• Birinci sətir bir boşluqla ayrılmış iki tam ədəd N və M ehtiva edir. • Növbəti N sətir hər bir şokolad parçasında nə qədər kişmiş olduğunu təsvir edir. Bu N sətirdən k-cisi plitənin k-cı sırasını təsvir edir. Hər belə sətir soldan sağa plitənin müvafiq sırasındakı M tam ədəd ehtiva edir. k-cı sıradakı (bu N sətir arasında) p-ci ədəd, k-cı sırada və p-ci sütunda yerləşən parçadakı kişmişlərin sayını bildirir.
Məhdudiyyətlər
1 <= N, M <= 50 hər bir tərəfdəki parça sayı, 1 <= R_{k,p} <= 1000 k-cı sırada və p-ci sütunda olan parçada kişmişlərin sayı.
Çıxış Məlumatları
Proqramınız standart çıxış axınına bir tam ədəd yazmalıdır: Boninin Petriyə ödəməli olduğu minimal kişmiş sayı.