Maximizing a Non‐Crossing Closed Knight Tour

A knight on a chessboard can move in an L–shaped pattern: two squares in one direction and one square in an orthogonal direction. In the classical knight's tour the knight is asked to visit every square exactly once and return to its starting square. In this problem the board is a rectangular m × n grid and an additional constraint is imposed: when we connect the centers of the squares visited in order the resulting polyline (or cycle when the knight returns to the start) should be simple (no two segments intersect or even touch, except at common endpoints of consecutive segments).

This extra restriction makes it impossible to cover all squares in general. Your task is to compute the maximum number of squares the knight can visit (including the starting square) while making a valid tour that starts and ends at the same square and never crosses or touches its own path (except at adjacent vertices). The centers of the squares are located at coordinates \((r+0.5, c+0.5)\) for a cell in row \(r\) and column \(c\), where rows are numbered \(0,1,\dots,m-1\) and columns \(0,1,\dots,n-1\).

Note: If no such closed tour exists, output 0.

inputFormat

The input consists of two space‐separated integers (m) and (n) representing the number of rows and columns of the chessboard respectively.

outputFormat

Output a single integer: the maximum number of squares the knight can visit in a closed non-crossing tour. If no valid tour exists, output 0.

sample

1 1

0