Göbələk yığımı#211
Bir yay səhərində fermer dostuna qonaq getmək üçün yola düşdü. Əliboş getməyin yaxşı olmadığını düşünən fermer, yol boyu dostu üçün dadlı, böyük göbələklər toplamaq qərarına gəldi. Bunun üçün o, böyük səbət götürdü və meşəyə yollandı. Fermer istəyir ki, yığdığı hər göbələk əvvəlkindən ağır olsun, axı bu daha maraqlıdır.
Meşə N \times M ölçülü düzbucaqlıdır (metr). Hər bir kvadratda tam bir göbələk bitir. Fermer mümkün qədər çox göbələk toplamaq istəyir və geriyə qayıtmadan (çünki dostuna gedir!) hər növbəti göbələk mütləq əvvəlkindən cənubda və şərqdə olmalıdır. Fermer göbələk yığmağa meşənin istənilən yerindən başlaya və bitirə bilər, sonra isə dostuna yollanır. Dost maksimum neçə göbələk hədiyyə ala bilər?
Birinci sətirdə iki natural və ədədi (1 \leq N, M \leq 500) — meşənin metrla uzunluğu və eni. Növbəti sətirdə hər birində ədəd — uyğun sahədəki göbələyin qramla çəkisi. Hər göbələyin çəkisi qramı aşmır.
Çıxışa bir ədəd yazın — dostun fermerdən alacağı maksimum göbələk sayı.
Nümunə 1