Milk Pails

Interview

Time limit2sMemory limit512 MB

Summary

Combine pours of sizes X and Y without exceeding M to get as close to M as possible.

Level: Easy2 of 10
Topics: Brute force
Solved: No attempts yet

Problem

Farmer John has an order for exactly $M$ units of milk ( $1 \le M \le 1000$ ) that he must fill right now. His milking machine just broke, so all he has are three pails of integer sizes $X$ , $Y$ , and $M$ ( $1 \le X < Y < M$ ). All three pails start empty. He may perform the following two operations any number of times, in any order.

Fill the smallest pail (size $X$ ) to the top with $X$ units of milk and pour it into the size- $M$ pail. He may do this only if the size- $M$ pail does not overflow.
Fill the medium pail (size $Y$ ) to the top with $Y$ units of milk and pour it into the size- $M$ pail. He may do this only if the size- $M$ pail does not overflow.

He may not be able to fill the size- $M$ pail all the way. Find the maximum amount of milk he can put into that pail.

Input

The first and only line contains $X$ , $Y$ , and $M$ , separated by spaces.

Output

Print the maximum amount of milk Farmer John can put into the size- $M$ pail.

Note

For $X = 17$ , $Y = 25$ , and $M = 77$ , pouring the size-17 pail three times and the size-25 pail once collects 76 units of milk.

Examples2

Example 1
Input
```
17 25 77
```
Expected output
```
76
```
Example 2
Input
```
2 4 5
```
Expected output
```
4
```