eolymp
bolt
Try our new interface for solving problems
Məsələlər

Göbələklər ardınca yürüş

Göbələklər ardınca yürüş

Zaman məhdudiyyəti 5 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Bir yay səhərində Kopatıç Kirpiyə qonaq getmək üçün yola düşdü. Kopatıç fikirləşdi ki, əliboş qonaq getmək nəzakətsizlikdir və ona görə də yol boyu öz dostu üçün dadlı böyük göbələklər toplamağı qərara aldı. Bunun üçün o, böyük hörmə səbət götürdü və meşəyə tərəf addımladı. Siçan istəyirdi ki, hər sonrakı göbələk çəkisinə görə əvvəlkindən böyük olsun, axı belə daha maraqlı idi.

Meşə Kroşanın hoppanmalarının ölçüsünə uyğun olaraq N*M (hK) ölçülü düzbucaqlı şəklindədir. Hər bir kvadrat hK-da düz bir dənə göbələk yetişir. Kopatıç geri qayıtmamaq şərti ilə (axı o, Kirpiyə qonaq gedir!) mümkün qədər daha çox göbələk yığmaq istəyir, başqa sözlə, Kopatıçın qopartdığı hər sonrakı göbələk əvvəlkindən cənubda və ya şərqdə yerləşməlidir. Kopatıç göbələk yığmağa meşənin istənilən yerindən başlaya və yığmanı dayandıra bilər, bundan sonra o, Kirpi gilə yollanır. Kirpi ən çox sayda neçə göbələk hədiyyə alacaq?

Giriş verilənləri

Birinci sətirdə iki natural N vəM (N,M500) ədəd - meşənin Kroşanın hoppanmaları ilə (hK) uzunluğu və eni verilir. Sonrakı N sayda sətrin hər birində M ədəd - uyğun sahədəki göbələyin qramla çəkisi verilir. Hər göbələyin çəkisi 1000 qramı aşmır.

Çıxış verilənləri

Çıxış faylında bir ədəd – Kirpinin Kopatıçdan alacağı ən çox sayda göbələyin sayı yerləşməlidir.

Nümunə

Giriş verilənləri #1
3 4
1 6 8 2
3 4 5 3
1 1 3 2
Çıxış verilənləri #1
2