레고 애호가의 삼각형

시간 제한: 1000 ms. 메모리 제한: 1024 MB.

레고 애호가가 2x4 레고 블록으로 삼각형 벽을 쌓으려 한다. 블록은 서로 엇갈리게 놓아서, 각 블록이 바로 위의 두 블록 각각과 절반(2x2 부분)씩 맞닿도록 한다. 벽의 치수는 정해져 있지만, 완성된 구조물에서 온전한 블록을 최대한 많이 쓰려면 블록을 어떻게 배치해야 할지 모른다.

삼각형 벽에서 한 변은 쌓아 올리는 바닥면이다. 두 번째 변은 그 바닥면에 수직이며, 한 층씩 건너서 블록의 절반이 잘려 있다. 세 번째 변은 앞의 두 변에서 주어진 눈금 사이로 레고를 잘라 만든다. 완성된 구조물에서 온전한 블록의 개수를 최대로 만드는 것이 목표다. 세로와 가로 치수는 주어지며, 어느 것이 세로이고 어느 것이 가로인지는 상관없다. 두 경우를 모두 확인해 더 나은 결과를 고른다.

표준 2x4 레고 블록은 길이 225 mm, 너비 112.5 mm(모서리가 깔끔하게 맞도록 길이의 절반), 두께(높이) 75 mm이다.

4 x 8(또는 8 x 4) 크기로 가능한 네 가지 구조. 온전한 블록은 붉은색으로 표시했다.

예시 사례는 8 x 4 배열을 지정한다. 더 정확히는 벽의 겹쳐 쌓는 구조를 반영하여 두께(75 mm) 개수와 절반 길이(112.5 mm) 개수를 지정한다. 이는 높이 8 x 75.0 mm = 600 mm, 길이 4 x 112.5 mm = 450 mm로 해석할 수 있다. 또는 높이 4 x 75.0 mm = 300 mm, 길이 8 x 112.5 mm = 900 mm로 해석할 수도 있다.

한 줄에 공백으로 구분된 두 정수가 주어진다. 이 정수들은 위에서 정의한 블록 배열의 크기다. 각 정수는 1 이상 1000 이하이다.

벽을 쌓는 데 사용할 수 있는 온전한 블록의 최대 개수를 정수 하나로 출력한다.