LOL P86108

En l’argot d’internet, LOL, l’acrònim anglès de “laughing out loud” (rient sonorament) s’utilitza freqüentment per descriure una situació suposadament divertida. A veure si aquest problema us sembla divertit...

Donats dos naturals $n$ i $m$, cal omplir una matriu $n \times m$ amb els caràcters ‘L’ i ‘O’, de tal manera que el nombre de “LOL”s que contingui sigui el màxim possible, comptant totes les aparicions horizontals, verticals i diagonals.

Per exemple, per a $n = 3$ i $m = 7$ la solució òptima és

LLLLLLL
OOOOOOO
LLLLLLL

amb 17 aparicions de “LOL”. Com un altre exemple, per a $n = 1$ i $m = 2$

OL

és una de les quatre solucions possibles, totes sense cap aparició de “LOL”.

Entrada

L’entrada consisteix en diversos casos, cadascun amb $n$ i $m$. Suposeu $1 \le n \le m$ i $n \cdot m \le 23$.

Sortida

Per a cada cas, escriviu el màxim nombre possible de “LOL”s.

Observació

No es valorarà cap solució que no sigui de força bruta.