Page not loading? Try clicking here.
Placeholder

#3971

Milk Pails 2s 512MB

Problems

Farmer John has received an order for exactly M units of milk (1 \leq M \leq 1,000) that he needs to fill right away. Unfortunately, his fancy milking machine has just become broken, and all he has are three milk pails of integer sizes X, Y, and M (1 \leq X < Y < M). All three pails are initially empty. Using these three pails, he can perform any number of the following two types of operations:

- He can fill the smallest pail (of size X) completely to the top with X units of milk and pour it into the size-M pail, as long as this will not cause the size-M pail to overflow.

- He can fill the medium-sized pail (of size Y) completely to the top with Y units of milk and pour it into the size-M pail, as long as this will not cause the size-M pail to overflow.

Although FJ realizes he may not be able to completely fill the size-M pail, please help him determine the maximum amount of milk he can possibly add to this pail.


Input

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


Output

Output the maximum amount of milk FJ can possibly add to the size-M pail.


Example 

17 25 77
76

In this example, FJ fills the pail of size 17 three times and the pail of size 25 once, accumulating a total of 76 units of milk.


Source

USACO 2016 February Bronze

You must sign in to write code.