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 × 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 ≤ n ≤ m i n · m ≤ 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.