Description

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

Input

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

Output

對每個測試用例輸出1行，即可以報銷的最大數額，精確到小數點后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的商品那就標記下表示此發票不可以報銷        }        }        if(r+t+y<=100000&&flag==0)        {            a[len++]=r+t+y;//加入這個數組當中這張發票可以報銷        }      }      for(i=0;i<len;i++)      {          for(j=m;j>=a[i];j--)          {              f[j]=max(f[j],f[j-a[i]]+a[i]);//求最大報銷額度          }      }      Q=f[m]*1.0/100;      printf("%.2f/n",Q);  }   return 0;}