교차하지 않는 나이트 투어

$8 \times 8$ 체스판의 모든 칸을 나이트로 도는 퍼즐은 잘 알려져 있다. 나이트는 한 방향으로 한 칸, 그와 직교하는 방향으로 두 칸 뛰어서만 움직인다. 나이트는 판의 모든 칸을 중복 없이 방문한 다음 출발한 칸으로 돌아와야 한다. 방법이 여러 가지이고 판도 작아서 사람이 손으로 풀 만하다.

여기서는 더 어려운 문제를 다룬다. 판은 $m \times n$ 직사각형이고, 나이트는 자기가 지나온 경로를 가로질러서는 안 된다. 나이트가 뛰어넘는 두 칸의 중심을 선분으로 이어 경로를 그린다고 하자. 이 선분들은 단순 다각형을 이루어야 한다. 즉 연속한 두 선분이 공통 끝점에서 맞닿는 경우를 빼면, 두 선분이 교차해서도 안 되고 서로 닿아서도 안 된다. 이 조건에서는 모든 칸을 방문할 수 없으므로, 대신 방문하는 칸의 수를 최대로 만들어야 한다. 출발한 칸으로 돌아와야 한다는 조건은 그대로 남는다.

그림 1은 $6 \times 6$ 판의 최적 투어다.

그림 1: $6 \times 6$ 판의 최적 투어.

첫째 줄에 직사각형 판의 크기를 나타내는 두 정수 $m$ ($1 \le m \le 8$)과 $n$ ($1 \le n \le 10^{15}$)이 주어진다.

$m \times n$ 판에서 경로가 교차하지 않는 나이트 투어가 방문할 수 있는 칸 수의 최댓값을 출력한다. 그런 투어가 없으면 $0$을 출력한다.