Description

有 $n$ 个杯子，每个杯子的容积是 $a$，且初始装有 $b$ 体积水。你可以进行任意次操作，每次操作选择任意两个杯子，将其中一个杯子内的水全部倒入另一个杯子中，但是过程中杯子里的水不能溢出（即不能超过其容积），如果不满足则无法进行该操作。

请通过合法的操作，最大化装有最多水的杯子里水的体积。

Format

Input

一行三个整数，表示 $a$，$b$，$n$。

Output

一行一个整数 $x$，表示最多水的杯子内的水的体积。

Samples

5 2 2

4

11 5 7

10

提示

样例1解释：假设现在有两个杯子A，B，可以先把A中的全部水倒入B中，此时A有0升水，B有4升水，结束操作。此时最多水杯子内水的数量为4。

数据范围：$1\leq n\leq 10^9，1\leq a\leq 10^{18}，1\leq b\leq min(a,10^9)$

python中一行输入三个整型数据可采用下列语句实现：

a,b,c=map(int,input().split())

来源

sxz