Description

有一种卡牌，数量为无限个，每个价格为 $v$ ，点数为 $1$ 。

你每次可以选择获得一张卡牌，花费 $v$ 的价格。

当你手中有两张及以上的卡牌时，对于任意两张卡牌你可以执行合并操作，将其点数合并且合并为一张纸牌，合并规则如下（设当前的两张卡牌点数为 $x,y$ ）：

$newcard=\begin{cases}x+y\\\frac{xy}{x+y}\end{cases}$

请问，如果你要凑成点数为 $\frac{p}{q}$ 的卡牌，最小花费是多少？

Input Format

一行三个整数表示 $p,q,v$ 。

Output Format

一行一个整数表示答案。

5 1 6​

30​

Hint

对于 $100\%$ 的数据，$0 \le p,q \le 10^{18}, v \le 100$