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