问题2044--牛奶桶

2044: 牛奶桶

[命题人 : ]
时间限制 : 1 sec  内存限制 : 128 MB

提交

题目描述

农夫约翰收到了一份牛奶订单,订购 M 单位的牛奶。

不幸的是,他的挤奶机刚刚坏掉了。

他只有三个桶,容积分别为 X, Y, M(1 ≤ X < Y < M)。

三个桶最初都是空的。

使用这三个桶,他可以执行以下两种类型的操作任意次数:

  1. 将最小的桶(容积为 X 的)装满牛奶,再将其中的牛奶全部倒入容积为 M 的桶中,前提是这不会导致容积为 M 的桶溢出牛奶。
  2. 将中号的桶(容积为 Y 的)装满牛奶,再将其中的牛奶全部倒入容积为 M 的桶中,前提是这不会导致容积为 M 的桶溢出牛奶。

虽然,约翰意识到他可能无法装满容积为 M 的桶,但请帮助他确定他可以添加到这个桶中的最大牛奶量。

输入

共一行,包含三个整数 X, Y, M
1 ≤ M ≤1000,
1 ≤ X < Y < M

输出

输出约翰可以添加到容积为 M 的桶中的最大牛奶量。

样例输入 Copy

17 25 77

样例输出 Copy

76

提示

在此样例中,约翰可将容积为 17 的桶装满 3 次倒入大桶中,将容积为 25 的桶装满 1 次倒入大桶中,总共添加了 76 单位牛奶。