Milk Pails

题目描述

农夫约翰收到了一个需要立刻完成的订单：恰好装满 $M$ 单位的牛奶（$1 \leq M \leq 1,000$）。不幸的是，他精致的挤奶机刚刚坏了，他现在只有三个整数容量的奶桶，大小分别为 $X$、$Y$ 和 $M$（$1 \leq X < Y < M$）。这三个奶桶起初都是空的。

使用这三个奶桶，他可以执行任意次数的以下两种操作：

• 他可以将最小的奶桶（容量为 $X$）完全装满至 $X$ 单位牛奶，并倒入容量为 $M$ 的奶桶中，前提是这不会导致容量为 $M$ 的奶桶溢出。
• 他可以将中等大小的奶桶（容量为 $Y$）完全装满至 $Y$ 单位牛奶，并倒入容量为 $M$ 的奶桶中，前提是这不会导致容量为 $M$ 的奶桶溢出。

尽管 FJ 意识到他可能无法将容量为 $M$ 的奶桶完全装满，请你帮助他确定他最多能向这个奶桶中加入多少牛奶。

输入格式

第一行也是唯一一行输入包含 $X$、$Y$ 和 $M$，用空格分隔。

输出格式

输出 FJ 最多能向容量为 $M$ 的奶桶中加入的牛奶总量。

17 25 77

76

提示

在这个例子中，FJ 将容量为 17 的奶桶装满三次，将容量为 25 的奶桶装满一次，总共累积 76 单位的牛奶。 Problem credits: Brian Dean

标签: USACO|2016|Bronze

来源

USACO|2016|Bronze