Water
题目描述
有 $n$ 个杯子,每个杯子的容积是 $a$,且初始装有 $b$ 体积水。
你可以进行任意次操作,每次操作选择任意两个杯子,将其中一个杯子内的水**全部倒入**另一个杯子中,但是过程中**杯子里的水不能溢出(即不能超过其容积)**,如果不满足则无法进行该操作。
请通过合法的操作,最大化装有最多水的杯子里水的体积。
输入输出格式
输入格式
一行三个整数,表示 $a,b,n$。
输出格式
一行一个整数 $x$,表示最多水的杯子内的水的体积。
输入输出样例
输入样例 #1
5 2 2
输出样例 #1
4
输入样例 #2
11 5 7
输出样例 #2
10
说明
#### 【样例 1 解释】
假设现在有两个杯子 $A,B$,可以先把 $A$ 中的全部水倒入 $B$ 中,此时 $A$ 有 $0$ 升水,$B$ 有 $4$ 升水,结束操作。此时最多水杯子内水的数量为 $4$。
#### 【数据规模与约定】
| 测试点编号 | $n\le$ | 特殊性质 |
| :----------: | :----------: | :----------: |
| $1\sim2$ | $10^5$ | 保证无论如何操作都不会溢出 |
| $3 \sim 6$ | $10^6$ | 无 |
| $7 \sim 10$ | $10^9$ | 无 |
对于 $100\%$ 的数据,$1 \le n \le 10^9$,$1\le a\le 10^{18}$,$1\le b\le \min(a,10^9)$。