#63 square

Loading problem...

Preparing the statement, recent submissions, and submit form.

Authors: lunarlity

Statement

크기가 $A \times B$ 인 직사각형이 있다.

이 직사각형을 여러 개의 정사각형 타일로 빈틈없이 채우려고 한다. 정사각형 타일은 다음과 같이 구매할 수 있다.

직사각형 전체를 정사각형 타일들로 빈틈없이 채울 때, 필요한 비용의 최솟값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$A\ B$

필요한 비용의 최솟값을 출력한다.

Input

6 4

Output

한 변의 길이가 $2$ 인 정사각형 타일 $6$ 개를 사용하면 비용은 $12$ 이다. 하지만 이것이 최적은 아니다.

대신 한 변의 길이가 $4$ 인 정사각형 타일 하나와 한 변의 길이가 $2$ 인 정사각형 타일 두 개로 채우면 비용은 $4+2+2=8$ 이며, 이것이 최소 비용임을 보일 수 있다.