Problem Description

There are $n$ cups. Each cup has capacity $a$, and initially contains water of volume $b$. You may perform any number of operations. In each operation, choose any two cups and pour all the water from one cup into the other cup, but during the process the water in the cup must not overflow (i.e., must not exceed its capacity). If this condition is not satisfied, then the operation cannot be performed.

Using legal operations, maximize the volume of water in the cup that contains the most water.

Input Format

One line with three integers $a, b, n$.

Output Format

One line with one integer $x$, representing the volume of water in the cup that contains the most water.

5 2 2 

4

11 5 7 

10

Hint

Sample 1 Explanation

Suppose there are two cups $A, B$. You can first pour all the water in $A$ into $B$. Then $A$ has $0$ liters of water and $B$ has $4$ liters of water, and the operations end. At this time, the amount of water in the fullest cup is $4$.

Constraints

For $100\%$ of the testdata, $1 \le n \le 10^9$, $1 \le a \le 10^{18}$, and $1 \le b \le \min(a, 10^9)$.

Translated by ChatGPT 5