A lame knight is located at the bottom-left corner of a height x width chessboard. Unlike a healthy knight, a lame knight can only make moves where he goes to the right. The only possible moves are:
The knight will make one trip, and he wants to maximize the number of visited cells. The knight's starting cell counts toward this number.
There is also one restriction for the knight's trip: it must contain each kind of a move at least once, unless it is shorter than 4 moves. If the knight makes less than 4 moves (thus visiting less than 5 cells), his moves are not limited in any way. Return the maximal number of cells the knight can visit during one trip, including the initial cell.
- 2 cells up, 1 cell right;
- 1 cell up, 2 cells right;
- 1 cell down, 2 cells right;
- 2 cells down, 1 cell right.