Ewokları əfv edin!
Cloud City-nin uğurlu mühasirəsindən sonra yenilənmiş İmperator Palpatine, Endor meşə ayında yeni bir İmperator bazasının tikintisinə başlamanızı tapşırıb. Lakin, Endor, 'Ewok' adlanan sevimli məxluqların yaşadığı bir yerdir.
Palpatine, soyuq ürəyində bu Ewoklara qarşı bir zəiflik hiss edərək, mövcud Ewok evlərinin heç birinin pozulmamasını əmr edib. Bundan əlavə, sizdən bazanın ümumi sahə baxımından mümkün qədər böyük olmasını istəyib və bu sahə üçə qədər düzbucaqlı bina arasında bölünə bilər. Palpatine-in qalaktik hökmranlıq axtarışında ona kömək edin!
Bu problem üçün sizə Endorun xəritəsi m×n düzbucaqlı şəbəkə şəklində verilir, burada bəzi hüceyrələr Ewok evləri kimi işarələnib, digərləri isə boşdur. Məqsədiniz bu şəbəkədə üçə qədər (lakin bəlkə də daha az) düzbucaqlı bina yerləşdirməkdir ki, heç bir bina bir-birinin üzərinə düşməsin və heç bir bina Ewok evinin üzərinə yerləşdirilməsin.
Giriş verilənləri
Giriş bir neçə test halını ehtiva edəcək. Hər bir test halı, şəbəkədəki sətir və sütunların sayını göstərən m və n tam ədədlərindən ibarət tək sətirlə başlayır (burada 1 ≤ m ≤ 250 və 1 ≤ n ≤ 250). Sonrakı m sətir Endorun xəritəsini müəyyən edir; xüsusilə, hər bir sətir n simvoldan ibarət olacaq, burada hər bir simvol ya boş yer üçün '.' (nöqtə), ya da Ewok evi üçün 'e' (kiçik hərf E) olacaq. Son test halından sonra "0 0" yazılmış tək bir sətir olacaq; bu sətir işlənməməlidir.
Çıxış verilənləri
Hər bir giriş test halı üçün binalarla örtülə biləcək maksimum sahəni göstərən tək bir tam ədəd çap edin.