hdu 1864最大清算額01リュックサック

//  0-1     
//  ，      ，  100 ，          ，  01  
//    ：Memory Limit Exceed 1 ，      1000 ，           1000 。
//  ：printf("%0.2lf
",(double)dp[(int)(all*100)]/100)         double  ，                
//AC Code
//6038113	2012-06-05 16:33:34	Accepted	1864	703MS	12268K	1244 B	G++	chen
#include<iostream>
#include<string>
#include<sstream>
using namespace std;

int bill[35];
int kind[3];
int N,n;
int dp[3000000];

double all;
string str;

int main(){
	while(cin>>all>>N&&N){
		//      
		memset(bill,0,sizeof(bill));
		for(int i=0;i<N;i++){
			cin>>n;
			memset(kind,0,sizeof(kind));
			//        
			while(n--){
				cin>>str;
				char tmp=str[0];
				if(tmp=='A'||tmp=='B'||tmp=='C'&&bill[i]!=-1){
					stringstream ss;
					ss<<str.substr(2,str.length()-2);
					double d;
					ss>>d;
					kind[tmp-'A']+=(int)(d*100);
				}
				else{
					bill[i]=-1;
				}
			}//end while
			//          
			double sum=0;
			if(bill[i]!=-1){
				for(int j=0;j<3;j++){
					if(kind[j]>60000){
						bill[i]=-1;
						break;
					}
					sum+=kind[j];
				}
				if(bill[i]!=-1){
					if(sum>100000){
						bill[i]=-1;
					}
					else{
						bill[i]=sum;
					}
				}
			}//end if
		}//end for
		//     ，      
		memset(dp,0,sizeof(dp));
		for(int i=0;i<N&&bill[i]!=-1;i++){
			for(int v=(int)(all*100);v>=bill[i];v--){
				dp[v]=max(dp[v],dp[v-bill[i]]+bill[i]);
			}
		}
		printf("%0.2lf
",(double)dp[(int)(all*100)]/100);
	}
	return 0;
}