One day, DD finds a strange hole with many treasures in it. He realizes that all the treasures are in pairs. Through deeply investigation, DD finds that there is some relation between each pair of treasures. One relation is just like DD and his girlfriend MM, if they are separated, both of them will lose values. The second relation is like DD and GG (a boy who loves MM), if they get together, a terrible thing will hapen, both treasures will lose values. The third relation is like DD and his shadow, it means that DD can‘t only choose shadow without himself, but DD can just choose himself without his shadow.

Every treasure has its own weight (W_i) and value (V_i), DD just has a broken package, it only allows W (or less) weight. And each treasures is unique, it means that DD can‘t choose a treasure twice. Another strange thing is all the weight of treasures are multiples of 100 (No one knows the reason).

Your task is to help DD to choose the treasures, DD wants the most values of treasure, so he can buy more present for MM.

Input

The input file will contain multiple test cases. The first line contains 2 integers W (0 <= W <= 5000000), N (0 <= N <= 10000). Following is N lines, each line contains 5 integers about two treasures‘ information and their relation, for example the ith line contains W_2i-1, V_2i-1, W_2i, V_2i, R_i (R_i=1 means the relation is like DD and MM, R_i=2 means the relation is like DD and GG, R_i=3 means the relation is like DD and his shadowm, the (2i-1)-th is like DD, and the (2i)-th is like his shadow). (We have 0 <= V_i <= 1000)

Output

For each case, you should print a single line with a single integer, the max value DD can have.

Sample Input

200 1
200 1 100 5 3
1000 3
200 2 300 3 1
300 5 300 6 2
600 1 200 5 3

Sample Output

1
11
 

题意：

给你背包容量和物品个数，怎样获得价值最多的物品。物品都是成双出现，有三种，第一种是 a和b都要一起选，第二种是a和b不能一起选，第三种是b依赖a（选b的话必须选a），物品的输入的格式是n行wa，va，wb，vb，种类 。

思路：

第一种的话就是将两种合成一种处理，第二种和第三种就类似分组背包了。

感想：

这题物品的weight可以为0，出题人你这么坑，大家知道么？一点都不符合实际情况，出题人的素质着急。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 1005
#define MAXN 50005
#define mod 1000000009
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;

int n,m,ans,cnt,tot,flag;
int dp[MAXN];
struct Node
{
    int w[2],v[2];
    int r;
}p[MAXN];

void ZeroOnePack(int w,int val)
{
    for(int i=m;i>=w;i--)
    {
        dp[i]=max(dp[i],dp[i-w]+val);
    }
}
void Pack(int w1,int v1,int w2,int v2)
{
    int ma;
    for(int i=m;i>=w1||i>=w2;i--)
    {
        ma=0;
        if(i>=w1) ma=max(ma,dp[i-w1]+v1);
        if(i>=w2) ma=max(ma,dp[i-w2]+v2);
        dp[i]=max(dp[i],ma);
    }
}
void solve()
{
    int i,j,t;
    memset(dp,0,sizeof(dp));
    for(i=1;i<=n;i++)
    {
        if(p[i].r==1)  // 两个都选
        {
            ZeroOnePack(p[i].w[0]+p[i].w[1],p[i].v[0]+p[i].v[1]);
        }
        else if(p[i].r==2) // 只能选一个
        {
            Pack(p[i].w[0],p[i].v[0],p[i].w[1],p[i].v[1]);
        }
        else // 选第二个必须选第一个
        {
            Pack(p[i].w[0],p[i].v[0],p[i].w[0]+p[i].w[1],p[i].v[0]+p[i].v[1]);
        }
    }
}
int main()
{
    int i,j,t;
    while(~scanf("%d%d",&m,&n))
    {
        m/=100;
        int w1,w2;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d%d%d%d",&w1,&p[i].v[0],&w2,&p[i].v[1],&p[i].r);
            p[i].w[0]=w1/100,p[i].w[1]=w2/100;
        }
        solve();
        ans=dp[m];
        printf("%d\n",ans);
    }
    return 0;
}

zoj 3264 Present for MM （坑题，写博客只是不想更多人被坑）