P1380 T-shaped Pentomino

We want to place T-shaped pentominoes on an $n\times m$ grid. The T-shaped pentomino can be rotated and specifically has the following four orientations ("#" represents a cell occupied by the T, "." represents a free cell): ```plain ### ..# .#. #.. .#. ### .#. ### .#. ..# ### #.. ``` What is the maximum number of non-overlapping T-shaped pentominoes that can be placed on an $n\times m$ grid?

A single line containing two integers $n,m$.

Output a single integer, the maximum number of T-shaped pentominoes that can be placed.

### Constraints For all testdata, $1\le n,m\le 9$. ### Sample Explanation  Translated by ChatGPT 5