Description

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):

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

What is the maximum number of non-overlapping T-shaped pentominoes that can be placed on an $n\times m$ grid?

Input Format

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

Output Format

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

5 6

4

Hint

Constraints

For all testdata, $1\le n,m\le 9$.

Sample Explanation

Translated by ChatGPT 5