[题目]T型骨牌

题目描述
在n×m的棋盘上，摆入T型，T型可以旋转，具体包括如下四个样式（“#”代表被T型占据的格子，“.”代表自由的格子）：
### ..# .#. #..
.#. ### .#. ###
.#. ..# ### #..
问最多能在 n×m的棋盘上摆入多少个不重叠的T型。
输入格式
两个数n，m。(1<=n,m<=9)
输出格式
一个数，最多能放入多少个T型
样例输入
5 6
样例输出
4
注释
样例说明：
A..C..
AAAC..
ABCCCD
.B.DDD
BBB..D
求解