Minimum Sum of Square Sides Partition

Given a rectangle with positive integer side lengths A and B, you are to partition the rectangle into one or more squares with positive integer side lengths such that the sides of the squares are parallel to the corresponding sides of the rectangle. There are many ways to tile the rectangle into squares. If the rectangle is partitioned into N squares with side lengths C₁, C₂, ..., C_N, you need to find the partition where the sum

\( \min = C_1 + C_2 + \dots + C_N \)

is minimized.

For instance, if the rectangle is already a square (i.e., \(A = B\)), the answer is simply \(A\). Otherwise, one effective approach is to use a greedy partition similar to the Euclidean algorithm: if \(A > B\), partition the rectangle by taking \(\lfloor \frac{A}{B} \rfloor\) squares of side \(B\) and then solve the remaining \((A - \lfloor \frac{A}{B} \rfloor \times B) \times B\) rectangle recursively. A similar process applies when \(B > A\).

inputFormat

The input consists of a single line containing two positive integers A and B (\(1 \leq A, B \leq 10^9\)), representing the side lengths of the rectangle.

outputFormat

Output a single integer denoting the minimum possible sum of the side lengths of all squares used in the partition.

sample

4 4

4