面包師Lavrenty打算用餡料做幾個(gè)面包，然后把它們賣掉。

Lavrenty有克面團(tuán)和種不同的餡料。餡料種類的下標(biāo)從，他知道他的第種餡料剩下 克，做一個(gè)第種餡料的面包，恰恰需要克的種餡料和克的面團(tuán)，同時(shí)這種面包可以賣塊錢。

他也可以做沒(méi)有餡的面包。每個(gè)這樣的面包需要克面團(tuán)，可以賣塊Tugrik。所以Lavrenty可以做任何數(shù)量的包子，用不同的餡料或者不用餡料，除非用完了面團(tuán)和餡料。Lavrenty會(huì)扔掉烘培面包后剩下的所有多余材料。

求出Lavrenty可以賺取的錢的最大數(shù)量。

輸入格式

第一行4個(gè)整數(shù)n,m,
接下來(lái)m行每行四個(gè)整數(shù)

輸出格式

輸出Lavrenty可以賺取的最大錢數(shù)

樣例輸入

10 2 2 1
7 3 2 100
12 3 1 10

樣例輸出

241

題解

很好的一道多重背包模板，然而卻似乎沒(méi)有很多人做？
這里放上兩份代碼，一份詳細(xì)一份簡(jiǎn)單

#include<bits/stdc++.h>
#define maxm 50
#define maxn 1500
#define maxa 150
using namespace std;
inline char get(){
    static char buf[3000],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,3000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    register char c=get();register int f=1,_=0;
    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
    return _*f;
}
int n,m;//n表示面團(tuán)總數(shù)，m表示餡料種類 
int a[maxn],d[maxn],b[maxn],c[maxn];
/*
a表示第i種餡料剩余數(shù)量 
b表示第i種要的餡料數(shù)量
c表示第i種要的面團(tuán)數(shù)量
d表示收益 
*/
int dp[maxm][maxn];//第一維遍歷面包種類，第二維遍歷面團(tuán)
int num;
int note[maxm][maxn];
int main(){
    //freopen("1.txt","r",stdin);
    n=read();m=read();
    c[1]=read();d[1]=read();a[1]=0;b[1]=0;
    //cout<<n<<m<<endl;
    int out=-1;
    for(register int i=2;i<=m+1;i++)a[i]=read(),b[i]=read(),c[i]=read(),d[i]=read();
    for(register int i=1;i<=m+1;i++){//遍歷面包種類 
        for(register int j=0;j<=n;j++){//遍歷面團(tuán)重量
            for(register int k=0;k*b[i]<=a[i] && k*c[i]<=n;k++){
                if(j>=c[i]*k){
                    dp[i][j]=max(dp[i-1][j-c[i]*k]+d[i]*k,dp[i][j]);
                }
            }
            //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
            out=max(out,dp[i][j]);
        }
    }
    cout<<out<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1500],d[1500],b[1500],c[1500];
int dp[15][1500];
int main(){
    n=read();m=read();
    cin>>c[1]>>d[1];a[1]=0;b[1]=0;
    for(int i=2;i<=m+1;i++)a[i]=read(),b[i]=read(),c[i]=read(),d[i]=read();
    for(int i=1;i<=m+1;i++){
        for(int j=0;j<=n;j++){
            for(int k=0;k*b[i]<=a[i] && k*c[i]<=n;k++){
                if(j>=c[i]*k)dp[i][j]=max(dp[i-1][j-c[i]*k]+d[i]*k,dp[i][j]);
            }
            out=max(out,dp[i][j]);
        }
    }
    cout<<out<<endl;
    return 0;
}