Uncrossed Knight's Tour

Time limit2sMemory limit1024 MB

Summary

Given an m by n board (m at most 8, n up to 1e15), find the maximum number of squares a closed knight tour can visit without crossing itself.

Level: Hard9 of 10
Topics: Greedy, Dynamic programming, Math, Implementation
Solved: No attempts yet

Problem

A well-known puzzle is to tour all the squares of an $8 \times 8$ chessboard with a knight, a piece that moves only by jumping one square in one direction and two squares in an orthogonal direction. The knight must visit every square of the board, without repeats, and then return to its starting square. There are many ways to do this, and the board is small enough that a person can solve the puzzle by hand.

This is a harder version, played on a rectangular $m \times n$ board with one extra constraint: the knight may never cross its own path. Picture the path as straight line segments joining the centers of the squares the knight jumps between. Those segments must form a simple polygon, so no two segments intersect or touch, except that consecutive segments touch at their common end point. Under this constraint the knight cannot reach every square, so you must instead maximize the number of squares it visits. The knight must still return to its starting square.

Figure 1 shows an optimal tour on a $6 \times 6$ board.

An optimal uncrossed closed knight tour on a 6 by 6 board

Figure 1: An optimal tour on a $6 \times 6$ board.

Input

The input consists of a single line containing two integers $m$ ( $1 \le m \le 8$ ) and $n$ ( $1 \le n \le 10^{15}$ ), the dimensions of the rectangular board.

Output

Display the largest number of squares that a knight can visit in a tour on an $m \times n$ board that does not cross its own path. If no such tour exists, display $0$ .

Examples4

Example 1
Input
```
6 6
```
Expected output
```
12
```
Example 2
Input
```
8 3
```
Expected output
```
6
```
Example 3
Input
```
7 20
```
Expected output
```
80
```
Example 4
Input
```
2 6
```
Expected output
```
0
```