描述

日暮堂前花蕊娇，

争拈小笔上床描，

绣成安向春园里，

引得黄莺下柳条。

——胡令能《咏绣障》

古时女子四德中有一项——女红。女红的精巧程度对于女子来说是十分重要的。韵哲君十分爱好女红，尤其是刺绣。

当衬衣公司的Immortal掌柜在知道韵哲君有这一手艺后，交给韵哲君一个任务：在他所提供的各种各样大小的布上绣上精美的花纹（每匹布上只能绣一种花纹）。有3种花纹可以供韵哲君选择，每一体积布上的每种花纹的美观度c和所占体积v都不同。Immortal带了一个不知道是否足够装下所有刺绣作品的包，请你帮忙计算一下，Immortal的包里所能装下作品的最大美观度。

输入

第一行为两个数n（布的匹数，0<n<=100）、m（包的容积，0<m<=8000）；

第二行到第四行，每行有3个数据：花纹种类编号z（0<z<maxint）、每一体积布上这种花纹的美观度c[z]（0<c[z]<maxint）和每一体积布上绣的这种花纹的体积v[z]（0<z<maxint）；

第五行到n+4行每行有2个数据，分别是第i匹布的体积b[i]（0<b[i]< maxint）和这匹布上所绣花纹的种类编号z[i]。

输出

输出一个正整数，为Immortal的包里所能装下作品的最大美观度。

输入样例 1 

5 100
8 2001 5
4 9 8
3 74 4
111 4
79 8
6 3
5 8
23 4

输出样例 1

10449

题解：

裸的0-1背包

//
//  main.cpp
//
//
//  Created by Edwin on 2019/2/25.
//  Copyright © 2019 Edwiv. All rights reserved.
//
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<a;++i)
#define FORD(i,a,b) for(int i=a;i>=b;--i)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
const int maxn=10000+10;
using namespace std;

int main(){
    int n,bag;
    int dp[maxn],v[maxn],w[maxn];
    map<int,int> mpc,mpv;
    sc2(n,bag);
    mst(v,0);
    mst(w,0);
    mst(dp,0);
    FF(i,3){
        int z,c,v;
        scanf("%d%d%d",&z,&c,&v);
        mpc[z]=c;
        mpv[z]=v;
    }
    FF(i,n){
        int op;
        sc2(v[i],op);
        w[i]=v[i]*mpc[op];
        v[i]+=v[i]*mpv[op];
        //cout<<v[i]<<" "<<w[i]<<endl;
    }
    for(int i=0;i<n;i++)
        for(int j=bag;j>=v[i];--j){
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    cout<<dp[bag]<<endl;
    
    return 0;
}