C. Аж ахуйн эрхлэгчид тусална уу

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Холын холын улсад энэ жил хожуу намар болжээ. Ургац хураалт арвин сайхан байсан бөгөөд одоо өвөлдөө бэлдэх цаг болсон байв. Ихэнх хүмүүс ургац хураалтын баяр тэмдэглэж байгаа учраас ах ахуйн эрхлэгч Саймон агуулах дотор газар тариалангийн хэрэгслүүдийг хийх газар олох хэрэгтэй болжээ.

Тэрээр нэгэн том овор бүхий хэрэгсэл болох тракторыг хийх газар олох тал дээр дараах асуудалтай учирчээ. Асуудлын гол нь тракторыг агуулахад хийхэд энэ нь энгийн тэгш өнцөгт хэлбэртэй зай эзлэхгүйд байв. Энэ нь Т-хэлбэр бүхий зайг эзлэх бөгөөд боломжит байрлалуудыг доорх зурагт дүрслэв (энд "#" гэсэн тэмдэгт нь тракторын зогсож байгаа хэсгийг илэрхийлэх ба "." гэсэн тэмдэгт нь хоосон зайг илэрхийлэх юм):

###      ..#      .#.      #..  
.#.      ###      .#.      ###  
.#.      ..#      ###      #..

$ $

Саймон жинхэнэ сорилттой тулгарчээ: өгөгдсөн $n × m$ ширхэг нүд бүхий агуулах дотор боломжит хамгийн их тооны тракторуудыг байрлуулах юм. Та тракторуудыг байрлуулахдаа тэдгээрийг ямар ч байдлаар эргүүлэн (ингэснээр та дээрх зурагт дүрсэлсний дагуу 4-н янзаар байрлуулж болох юм) байрлуулж болох ажээ. Тэгсэн хэдий ч 2 трактор нь хоорондоо давхцаж болохгүй ба өөрөөр хэлбэл тэд агуулах дотор байх ижил нүдийг хуваан хэрэглэж болохгүй юм.

Саймон агуулах дотор оновчтой байдлаар хамгийн олон тооны трактор байрлуулахад хэтэрхий ганцаардаж байлаа. Та түүнд тусалж чадах уу?

Оролт

Оролтын ганц мөрөнд зайгаар тусгаарлагдсан 2 бүхэл тоо $n$ болон $m$ ($1 ≤ n, m ≤ 9$) өгөгдөх ба эдгээр нь агуулахын хэмжээнүүдийг илэрхийлнэ.

Гаралт

Гаралтын эхний мөрөнд агуулах дотор байрлуулж болох хамгийн их тракторын тоог хэвлэнэ үү. Дараагийн $n$ ширхэг мөрийн мөр болгонд $m$ ширхэг тэмдэгт хэвлэнэ. "." (цэг)-ээр хоосон зайг илэрхийлэх бөгөөд дараалсан Латин том үсгүүдээр агуулахад оновчтой байдлаар байрлаж буй тракторуудыг тэмдэглэнэ үү. Ингэхдээ нэг тракторыг зөвхөн нэг үсэг ашиглан тэмдэглэх бөгөөд эхний тракторыг "A"-аар, 2-дахь тракторыг "B"-ээр гэх мэтчилэн хэдэн ширхэг трактор байрлуулсан байна бүгдийн энэ маягаар тэмдэглэх юм. Байрлуулсан тракторуудаа хэрхэн дугаарлах нь таны сонголт бөгөөд хэрэв өгөгдсөн агуулахын хэмжээний хувьд хэд хэдэн боломжит хариултууд оршин байвал тэдгээрийн алийг нь ч хэвлэсэн болно.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
3 3
Гаралт
1
AAA
.A.
.A.
Оролт
5 6
Гаралт
4
A..C..
AAAC..
ABCCCD
.B.DDD
BBB..D
Оролт
2 2
Гаралт
0
..
..
Сэтгэгдлүүдийг ачааллаж байна...