m * n 크기의 나무판이 있습니다. 무사(武士)의 후손인 영찬이는 이 나무판을 자르고 싶어합니다.

조상으로부터 대대로 내려온 장미문양 식칼을 든 영찬이는 다음 규칙에 맞추어 칼질을 정확히 k번 할 것입니다.

- 모든 칼질은 수평 또는 수직이어야 합니다.

- 모든 칼질은 격자점을 지나야 합니다. 즉, 1*1 짜리 나무판 조각을 자를 수 없습니다.

- 영찬이는 손이 빠르기 때문에, 모든 칼질은 한꺼번에 이루어집니다.

즉, 나무판이 가로로 잘려 두 조각이 되었다고 하더라도, 세로로 그들을 한꺼번에 자를 수 있습니다.

위 그림은 5*6 크기의 나무판을 가로로 두 번, 세로로 세 번 총 5번 자른 예시입니다.

영찬이는 가장 작은 조각을 가능한 한 크게 하고 싶어합니다. 그 넓이를 구해 보세요.

나무판 자르기 timer 1s memory 128MB

나무판 자르기 1s 128MB