크기가 인 직사각형이 있다.
이 직사각형을 여러 개의 정사각형 타일로 빈틈없이 채우려고 한다. 정사각형 타일은 다음과 같이 구매할 수 있다.
- 비용 를 지불하면, 크기의 정사각형 타일을 개 받는다.
직사각형 전체를 정사각형 타일들로 빈틈없이 채울 때, 필요한 비용의 최솟값을 구하여라.
Input
입력은 다음과 같은 형식으로 주어진다.
Output
필요한 비용의 최솟값을 출력한다.
Constraints
- .
- .
Subtasks
Samples
입력
6 4
출력
8
한 변의 길이가 인 정사각형 타일 개를 사용하면 비용은 이다. 하지만 이것이 최적은 아니다.
대신 한 변의 길이가 인 정사각형 타일 하나와 한 변의 길이가 인 정사각형 타일 두 개로 채우면 비용은 이며, 이것이 최소 비용임을 보일 수 있다.