병든 나이트
시간 제한2초메모리 제한128 MB
N×M 체스판에서 네 가지 특수한 나이트 이동만 가능한 기사가 방문 가능한 최대 칸 수를 구하며, 4회 이상 이동 시 네 방향을 모두 써야 합니다.
문제
병든 나이트는 N x M 크기의 체스판에서 가장 왼쪽 아래 칸에 서 있다. 일반 나이트와 달리 다음 네 가지 방법으로만 이동할 수 있다.
- 위로 2칸, 오른쪽으로 1칸
- 위로 1칸, 오른쪽으로 2칸
- 아래로 1칸, 오른쪽으로 2칸
- 아래로 2칸, 오른쪽으로 1칸
병든 나이트는 여행하면서 방문하는 칸 수를 최대화하려고 한다. 단, 이동 횟수가 4번 이상이라면 위의 네 가지 이동 방법을 각각 적어도 한 번씩 사용해야 한다. 이동 횟수가 3번 이하라면 이동 방법에는 추가 제약이 없다.
체스판의 크기 N과 M이 주어질 때, 병든 나이트가 방문할 수 있는 칸 수의 최댓값을 구하시오.
입력
첫째 줄에 체스판의 세로 길이 N과 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다.
출력
병든 나이트가 여행에서 방문할 수 있는 칸 수의 최댓값을 출력한다.