http://poj.org/problem?id=3211

//01    ：         ，               ，         。
//                  
//  ：                   ，        ，           。                  
//                     sumTime,   sumTime/2              。      
//dp[j]=max(dp[j],dp[j-time[i]]+time[i])
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string.h>
using namespace std;
struct node
{
    int time;
    int flag;
    char  col[20];
} Node[1020];
int dp[5020];
int num[5020];//              
int d;
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int m,n,judge,ans,nn,sumTime;
    char  test[20];
    char  tem[10][20];
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        ans=0;
        d=nn=0;
        memset(Node,0,sizeof(Node));
        if(m==0&&n==0)
            break;
        for(int i=0; i<m; i++)
        {
            cin>>tem[i];
        }
        for(int i=0; i<n; i++)
        {
            cin>>Node[i].time;
            cin>>Node[i].col;
        }
        for(int i=0; i<m; i++)
        {
            sumTime=0;
            d=0;
            // strcpy(test,tem[i]);
            for(int j=0; j<n; j++)
                if(strcmp(Node[j].col,tem[i])==0&&Node[j].flag==0)
                {
                    num[d++]=Node[j].time;
                    sumTime+=Node[j].time;
                    Node[j].flag=1;
                }
            if(sumTime==0)
                 continue;
            for(int j=sumTime/2; j>=0; j--)
                  dp[j]=0;
            for(int k=0; k<d; k++)
                for(int j=sumTime/2; j>=num[k]; j--)//             。
                     dp[j]=max(dp[j],dp[j-num[k]]+num[k]);
            ans+=sumTime-dp[sumTime/2];
        }
        printf("%d
",ans);
    }
    return 0;
}