Codeforces 106 Buns【다중 가방】

참고 자료:
https://blog.csdn.net/qq_37748451/article/details/86486389
제목:
Lavrenty, a baker, is going to make several buns with stuffings and sell them.
Lavrenty has n grams of dough as well as m different stuffing types. The stuffing types are numerated from 1 to m. Lavrenty knows that he has ai grams left of the i-th stuffing. It takes exactly bi grams of stuffing i and ci grams of dough to cook a bun with the i-th stuffing. Such bun can be sold for di tugriks.
Also he can make buns without stuffings. Each of such buns requires c0 grams of dough and it can be sold for d0 tugriks. So Lavrenty can cook any number of buns with different stuffings or without it unless he runs out of dough and the stuffings. Lavrenty throws away all excess material left after baking.
Find the maximum number of tugriks Lavrenty can earn.
Input
The first line contains 4 integers n, m, c0 and d0 (1 ≤ n ≤ 1000, 1 ≤ m ≤ 10, 1 ≤ c0, d0 ≤ 100). Each of the following m lines contains 4integers. The i-th line contains numbers ai, bi, ci and di (1 ≤ ai, bi, ci, di ≤ 100).
Output
Print the only number — the maximum number of tugriks Lavrenty can earn.
Examples
Input

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

Output

241

Input

100 1 25 50
15 5 20 10

Output

200

Note
To get the maximum number of tugriks in the first sample, you need to cook 2 buns with stuffing 1, 4 buns with stuffing 2 and a bun without any stuffing.
In the second sample Lavrenty should cook 4 buns without stuffings.
제목 대의:
반죽이 n이고 M종의 파이를 곁들인다. C0, D0을 주면 밀가루 C0으로 찐빵을 찌면 D0원에 팔 수 있다는 뜻이다.
그 후 M행, i행 Ai는 i소의 소가 얼마나 있는지, 비는 i종 파이를 만드는 데 소가 얼마나 필요한지, Ci는 이 떡에 면이 얼마나 필요한지, 디는 이 떡이 얼마에 팔릴 수 있는지 표시했다.총가치가 최대로 얼마인지를 구하다.
문제 해결 방법:
누드 다중 DP(등보).
dp[i][j][k], i종의 조미료는 j*c그램을 사용하여 k그램의 밀가루를 혼합하여 생성하는 가치를 나타낸다. i종의 조미료는 우리가 for순환통제를 사용할 수 있다. j*b그램의 i밀가루는 k그램의 조미료와 대응한다. 즉, dp의 값은 마지막 단계에서 통제되기 때문에 j*b도 순환으로 표시할 수 있기 때문에 마지막 dp는 1차원이다.
구현 코드:
   

#include
#include
#include
#include
#define ll long long
using namespace std;
int main()
{
    int n,m,c0,d0,a,b,c,d;
    int dp[10010];
    memset(dp,0,sizeof(dp));
    cin>>n>>m>>c0>>d0;
    for(int i=c0;i<=n;i++)
        dp[i]=i/c0*d0;
   
    for(int i=0;i>a>>b>>c>>d;    
        for(int j=1;j<=a/b;j++)    //  i        
           for(int k=n;k>=c;k--)   //      
             dp[k]=max(dp[k-c]+d,dp[k]);
    }
    cout<