Description

現(xiàn)有一筆經(jīng)費(fèi)可以報(bào)銷一定額度的發(fā)票。允許報(bào)銷的發(fā)票類型包括買圖書（A類）、文具（B類）、差旅（C類），要求每張發(fā)票的總額不得超過1000元，每張 發(fā)票上，單項(xiàng)物品的價值不得超過600元。現(xiàn)請你編寫程序，在給出的一堆發(fā)票中找出可以報(bào)銷的、不超過給定額度的最大報(bào)銷額。

Input

測試輸入包含若干測試用例。每個測試用例的第1行包含兩個正數(shù) Q 和 N，其中 Q 是給定的報(bào)銷額度，N（<=30）是發(fā)票張數(shù)。隨后是 N 行輸入，每行的格式為：m Type_1:PRice_1 Type_2:price_2 ... Type_m:price_m其中正整數(shù) m 是這張發(fā)票上所開物品的件數(shù)，Type_i 和 price_i 是第 i 項(xiàng)物品的種類和價值。物品種類用一個大寫英文字母表示。當(dāng)N為0時，全部輸入結(jié)束，相應(yīng)的結(jié)果不要輸出。

Output

對每個測試用例輸出1行，即可以報(bào)銷的最大數(shù)額，精確到小數(shù)點(diǎn)后2位。

Sample Input

Sample Output

#include<iostream>#include<cstdio>#include<cstring>using namespace std;int f[3000001];int main(){  double Q,p;  int n,m,k,i,g,r,t,y,flag,len,j;  char c;  int a[110];  while(~scanf("%lf%d",&Q,&n))//輸入限定的額度和有幾件物品  {      if(n==0)        break;        memset(a,0,sizeof(a));        memset(f,0,sizeof(f));        len=0;      m=(int)(Q*100);      for(i=0;i<n;i++)      {          scanf("%d",&k);          r=0,t=0,y=0;          flag=0;        while(k--)        {         scanf(" %c:%lf",&c,&p);         g=(int)(p*100);        if(c=='A'&&r+g<=60000)        {                r+=g;//判斷同一類商品是不是超過了600元        }        else if(c=='B'&&t+g<=60000)        {                t+=g;        }        else if(c=='C'&&y+g<=60000)        {                y+=g;        }        else        {            flag=1;//如果超過了或者有其他不屬于A,B,C的商品那就標(biāo)記下表示此發(fā)票不可以報(bào)銷        }        }        if(r+t+y<=100000&&flag==0)        {            a[len++]=r+t+y;//加入這個數(shù)組當(dāng)中這張發(fā)票可以報(bào)銷        }      }      for(i=0;i<len;i++)      {          for(j=m;j>=a[i];j--)          {              f[j]=max(f[j],f[j-a[i]]+a[i]);//求最大報(bào)銷額度          }      }      Q=f[m]*1.0/100;      printf("%.2f/n",Q);  }   return 0;}