题目描述
Problem Description
There are $n$ cups, each with a capacity of $a$ and initially containing $b$ volume of water.
You can perform any number of operations. Each operation involves choosing any two cups and pouring all the water from one cup into the other, provided that the water does not overflow (i.e., does not exceed the cup's capacity). If this condition is not met, the operation cannot be performed.
Please maximize the volume of water in the cup with the most water through legal operations.
Input Format
A single line containing three integers: $a, b, n$.
Output Format
A single line containing an integer $x$, representing the volume of water in the cup with the most water.
Sample Input and Output
Sample Input #1
5 2 2
Sample Output #1
4
Sample Input #2
11 5 7
Sample Output #2
10
Notes
Sample 1 Explanation
Assume there are two cups $A$ and $B$. You can pour all the water from $A$ into $B$, resulting in $A$ having $0$ liters of water and $B$ having $4$ liters of water. The operation ends here, and the cup with the most water contains $4$ liters.
Data Range and Constraints
| Test Case Number | $n\le$ | Special Property |
|---|---|---|
| $1\sim2$ | $10^5$ | Guaranteed that no overflow occurs regardless of the operations |
| $3 \sim 6$ | $10^6$ | None |
| $7 \sim 10$ | $10^9$ | None |
For $100\%$ of the data, $1 \le n \le 10^9$, $1 \le a \le 10^{18}$, $1 \le b \le \min(a, 10^9)$.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分