P10056 Water

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.

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

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

#### 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 | Test Point ID | $n \le$ | Special Property | | :----------: | :----------: | :----------: | | $1 \sim 2$ | $10^5$ | It is guaranteed that no matter how you operate, overflow will never occur. | | $3 \sim 6$ | $10^6$ | None. | | $7 \sim 10$ | $10^9$ | None. | 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