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

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

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

三个桶最初都是空的。

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

将最小的桶（容积为 X 的）装满牛奶，再将其中的牛奶全部倒入容积为 M 的桶中，前提是这不会导致容积为 M 的桶溢出牛奶。 将中号的桶（容积为 Y 的）装满牛奶，再将其中的牛奶全部倒入容积为 M 的桶中，前提是这不会导致容积为 M 的桶溢出牛奶。 虽然，约翰意识到他可能无法装满容积为 M 的桶，但请帮助他确定他可以添加到这个桶中的最大牛奶量。

输入格式

共一行，包含三个整数 X,Y,M。

输出格式

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

数据范围

1≤M≤1000,

1≤X<Y<M

输入样例：

17 25 77

输出样例：

76

样例解释

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

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int res[N];
int main()
{
    int x,y,m,a,b;
    cin>>x>>y>>m;
    a=m/x;
    b=m/y;
    int maxt=0,ans;
    for(int i=0;i<=a;i++) {
        ans=i*x;;
        for(int j=0;j<=b;j++) {
           if(j) ans+=y;
           if(ans>m) break;
           else {
            maxt=max(maxt,ans);
           }
      }
    }
    cout<<maxt;
    return 0;
}


**直接转换为dp完全背包一维优化**
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1010;
int f[N];
int w[3], v[3];
int main()
{
    int x, y, m;
    for(int i = 1; i <= 2; i++) cin >> w[i], v[i] = w[i];
    cin >> m;
    for(int i = 1; i <= 2; i++)
        for(int j = v[i]; j <= m; j++)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m];
    return 0;
}



#include<iostream>
using namespace std;
int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    int ans=-0x7f7f7f7f;
    int t;
    for(int i=0;i*b<=c;i++)t=(c-i*b)/a,ans=max(ans,i*b+a*t);
    cout<<ans<<endl;
    return 0;
}