Masala #0189

Xotira 16 MB Vaqt 1000 ms

Plyus * Plyus

Sizga \(N \times M\) o’lchamli jadval berilgan, har bir elementi yaxshi (good - G) yoki yomon (bad - B) ni ifodalaydi.

To’g’ri Plyus deb gorizontal va vertikal uzunliklari teng, bu uzunlik toq, chiziqlar o’zaro teng markazdan kesishganiga aytiladi. Plyusning yuzasi u egallab turgan yacheykalar soniga teng. Quyidagi diagrammada yashil maydonlar Plyus hisoblanadi, sariq maydonlar esa Plyus hisoblanmaydi.

Sizga berilgan jadvaldan tomonlari faqat yaxshi elementlardan iborat bo’ladigan shunday ikkita Plyusni ajratib olingki, ajratilgan Plyuslar jadvalda umumiy nuqtaga ega bo’lmasin va ikkila Plyusning yuzalari ko’paytmasi maksimal bo’lsin.

Kiruvchi ma'lumotlar:

Dastlabki satrda ikkita butun son, \(N\) va \(M(2 \le N, M \le 15)\) sonlari, jadvalning qatorlar va ustunlar soni kiritiladi. Keyingi qatordan boshlab \(N\) ta qatorning har birida \(M\) tadan belgi, jadvalning elementlari kiritiladi.

Chiquvchi ma'lumotlar:

Umumiy koordinataga ega bo’lmagan holda ajratib olingan ikkita Plyusning yuzalari ko’paytmasi maksimal necha bo’lishini chop eting.

Misollar

#	input.txt	output.txt
1	5 6 GGGGGG GBBBGB GGGGGG GGBBGB GGGGGG	5
2	6 6 BGBBGB GGGGGG BGBBGB GGGGGG BGBBGB BGBBGB	25

Izoh:

Quyidagi rasmning chap tomonidagi jadvalda 1-test, o’ng tomondagi jadvalda 2-test bo’yicha ikkita Plyus qanday ajratib olinganligini ko’rishingiz mumkin: