Problem7686--USACO 2016 February Contest, Bronze —— Problem 1. Milk Pails

7686: USACO 2016 February Contest, Bronze —— Problem 1. Milk Pails

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

Farmer John has received an order for exactly $M\ (1≤M≤1,000)$ units of milk 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, M\ (1≤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, M$, separated by spaces.

Output

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

Sample 1 Input

17 25 77

Sample 1 Output

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.

HINT

题目来源:USACO

Source/Category