#2334. 装牛奶[USACO16FEB] Milk Pails B

装牛奶[USACO16FEB] Milk Pails B

Farmer John has received an order for exactly M units of milk (1≤M≤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≤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.

FJ收到了一份正好是𝑀个单位的牛奶订单(1≤𝑀≤1,000),他需要马上装满。不幸的是,他的高级挤奶机刚刚坏了,他只有三个尺寸为X、Y和M的牛奶桶(1≤𝑋<𝑌<𝑀)。三个桶最开始都是空的。用这三个桶,他可以进行以下两类操作中的任何一个。

  • 他可以在最小的桶(尺寸为X)里完全装满X个单位的牛奶,然后在不导致尺寸为M的桶溢出的情况下倒入桶里。
  • 他可以在中型桶(尺寸为Y)里完全装满Y个单位的牛奶,然后在不导致尺寸为M的桶溢出的情况下倒入桶里。

虽然FJ意识到他可能无法完全装满𝑀号桶,但请帮助他确定他能够填满这个桶的最大牛奶量。

输入格式

第一行且只有一行包含三个整数𝑋,𝑌和𝑀,用空格隔开。

输出格式

输出FJ能够添加到𝑀号桶的最大牛奶量。

输入输出样例

17 25 77
76

数据范围与提示

在这个例子中,FJ填满了三次大小为17的桶;填满了一次大小为25的桶。这四次操作累计下来填满了大小为76的桶。