스네이크
시간 제한1초메모리 제한1024 MB
n x m 격자에서 이동하는 동안 머리와 꼬리가 항상 인접한 상태를 유지할 수 있는 뱀의 최대 길이를 구한다.
문제
흐즈로는 "스네이크"라는 고전 게임을 매우 좋아합니다. 스네이크는 다음과 같은 규칙에 따라 진행됩니다.
- 게임은 격자에서 진행됩니다. 이때, 이 축 길이, 이 축 길이입니다.
- 플레이어는 격자 위에서 연결된 칸 로 구성된 뱀을 상하좌우로 조종합니다. "연결됨"이라고 함은 인 모든 수에 대해 과 가 상하, 또는 좌우로 인접함을 의미합니다.
- 매 턴마다 뱀은 상하좌우 중 한 방향으로 이동합니다. 이 때, 뱀의 마지막 칸 (, 이하 "꼬리")이 사라지고, 뱀의 첫 칸 (, 이하 "머리")이 조종된 방향으로 한 칸 연장됩니다. 그 후 각 칸의 번호가 새롭게 정해집니다.
- 뱀은 동일한 칸을 동시에 두 번 이상 차지할 수 없습니다. 따라서, 뱀의 머리는 뱀이 지나고 있으면서 꼬리가 위치하지 않은 칸으로는 이동할 수 없습니다.
- 뱀의 머리는 뱀의 두번째 칸 ()이 있는 방향으로는 이동할 수 없습니다.
이 게임은 정말 간단하고 유명해서, 최적의 전략도 잘 알려져 있습니다. 바로 머리와 꼬리가 인접한 상태를 유지하면서 이동하는 것입니다! 흐즈로는 이러한 "최적의 전략"을 사용해 얼마나 긴 뱀을 안정적으로 유지할 수 있을지 궁금했습니다. 격자의 가로 길이 과 세로 길이 이 주어질 때, "최적의 전략"을 유지할 수 있는 가장 긴 뱀의 길이를 출력하세요.
입력
두 정수 과 이 한 줄에 공백으로 분리되어 주어집니다. ()
출력
문제의 정답을 출력하세요.