Pirate sandığı
Pirat Cek döyüşlərdən, qarətçilikdən, oğurluqdan və açıq dənizdə hər kəsə və hər yerdə təzyiq göstərməkdən yorulmuşdu. O, təqaüdə çıxmağa qərar verdi və hətta okeanda mükəmməl bir tənha ada tapdı ki, orada ömrünün qalan hissəsini layiqincə keçirəcək, əlbəttə ki, pulları tükənməsə. Hazırda onun çoxlu qızıl sikkələri var və onları bir sandığa yığmaq istəyir (axı o, piratdır!). Cek tam ədədi tərəfləri olan və sandığın dibinin müəyyən ölçüsünü keçməyən bir düzbucaqlı paralelpiped şəklində sandıq qura bilər. Yalnız sandığı xəzinə ilə harada gizlətmək lazım olduğunu tapmaq qalır.
Cek sandığı sakit bir gölməçədə batırmağa qərar verdi. Gölməçənin səthi müəyyən tərəfləri olan bir düzbucaqlıdır və gölməçə hər tərəfdən şaquli daş sahillərlə əhatə olunub. Cek gölməçənin dibini araşdırdı və hər bir 1x1 gölməçə kvadratının (Dekart koordinat sistemində) həmin yerdəki dərinliyini bilir. Cek sandığı batırdıqda, o, ən dərin yerə qədər batacaq, ta ki, dibə ən azı bir kvadratla toxunana qədər. Batırılmış sandıq səbəbindən gölməçədəki su səviyyəsi yüksələcək. Gölməçənin sahilləri kifayət qədər hündürdür ki, su heç vaxt onun sərhədlərindən kənara çıxmasın. Aydındır ki, sandıq gizlədilməlidir, yəni o, gölməçədəki su səviyyəsindən tamamilə aşağıda olmalıdır. Sizin vəzifəniz - gölməçədə gizlədilə biləcək maksimum həcmli sandığı tapmaqdır.
Sol tərəfdəki şəkildə sandıqsız gölməçə göstərilib, mərkəzdə - 3 həcmli sandıq olan gölməçə, sağda - gölməçədə maksimum mümkün 4 həcmli sandıq. Qeyd edək ki, mərkəzi şəkildəki sandıq bir vahid daha hündür olsaydı, onun üstü gölməçənin səthində görünərdi.
Şəkil: Giriş testi 1 üçün illüstrasiya.
Giriş verilənləri
Giriş məlumatları bir testdən ibarətdir. Test bir sətirdən başlayır, bu sətir dörd tam ədəd a, b, m, n (1 ≤ a, b, m, n ≤ 500) ehtiva edir. Gölməçənin səthinin ölçüləri - m×n, sandığın dibinin maksimum ölçüsü - a×b. Bundan əlavə, a və b kifayət qədər kiçikdir ki, sandıq heç vaxt bütün gölməçəni tamamilə örtməsin. Qalan m giriş sətirlərinin hər biri n ədəd d_{i,j} ehtiva edir, bu ədədlər (i,j) koordinatları ilə kvadratın gölməçədəki dərinliyini təsvir edir, burada 0 ≤ d_{i,j} ≤ 10^9 istənilən 1 ≤ i ≤ m, 1 ≤ j ≤ n üçün.
Çıxış verilənləri
Tam ədədi tərəfləri olan və gölməçədə su səthinin altında gizlədilə biləcək maksimum həcmli sandığı çıxarın, burada dibin ölçülərindən biri a-dan, digəri isə b-dən çox olmamalıdır. Əgər heç bir sandıq suyun altında gizlədilə bilməzsə, 0 çıxarın.