Description

July 17 is Mr. W’s birthday. To celebrate, ACM-THU plans to make an $M$-layer birthday cake with volume $N\pi$, where each layer is a cylinder.

Let the $i$-th layer from bottom to top ($1 \leq i \leq M$) be a cylinder with radius $R_i$ and height $H_i$. For $i \lt M$, it is required that $R_i \gt R_{i+1}$ and $H_i \gt H_{i+1}$.

Since the cake needs to be frosted, to save cost as much as possible, we want the area $Q$ of the cake’s outer surface (excluding the bottom face of the lowest layer) to be minimized.

Given $N$ and $M$, write a program to find a construction of the cake (appropriate values of $R_i$ and $H_i$) that minimizes $S=\dfrac{Q}{\pi}$.

(Except for $Q$, all the quantities above are positive integers.)

Input Format

The first line contains an integer $N$ ($N \leq 2 \times 10^4$), indicating that the cake’s volume is $N\pi$.

The second line contains $M$ ($M \leq 15$), the number of layers of the cake.

Output Format

Output an integer $S$. If there is no solution, output $0$.

100
2

68

Hint

Translated by ChatGPT 5