Ü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 düzülüb və $N$ sıra və $M$ sütun təşkil edir, ümumilikdə N \times M parça olur. Hər bir parçanın üzərində 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 N \times M 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ş edir. 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 Petrə mümkün qədər az ödəmək istəyir. O, N \times M parçaların hər birində nə qədər kişmiş olduğunu bilir. O, Petrə hansı hissələri vermək üçün sıranı seçə bilər və həmçinin Petrə 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ə Petrə 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 Petrə ödəməli olduğu minimal kişmiş sayını müəyyən edən bir proqram yazın.