1 /*
 2 Author:    Leo.W
 3 Descriptipn:典型的01背包問(wèn)題，對(duì)輸入的每組數(shù)據(jù)【花費(fèi)及可能性】進(jìn)行背包判斷，
 4             得到在花費(fèi)總和是經(jīng)濟(jì)能力范圍內(nèi)的累計(jì)獲offer幾率最大的組合。
 5 How to Do:f[V]=max{f[V],f[V-c[i]]+w[i]}; 
 6         【前后f[V]分別表示前i個(gè)大學(xué)申請(qǐng)?jiān)诳偦ㄙM(fèi)為V時(shí)的最大幾率和前i-1個(gè)大學(xué)申請(qǐng)?jiān)诳偦ㄙM(fèi)為V時(shí)的最大幾率；
 7             f[V-c[i]]表示前i-1個(gè)大學(xué)在總花費(fèi)為V-c[i]時(shí)的最大幾率，
 8             c[i]表示第i個(gè)大學(xué)申請(qǐng)的花費(fèi)，w[i]則表示第i個(gè)大學(xué)申請(qǐng)成功的幾率】
 9   */
10 #include <iostream>
11 #include <string.h>
12 using namespace std;
13 double f[100010];
14 int c[1010];
15 double w[1010];
16 int main(){
17     //freopen("in.txt","r",stdin);
18     int n,m;
19     int i,j;
20     while(scanf("%d%d",&n,&m),m||n){
21         for(i=0;i<m;i++){
22             scanf("%d%lf",&c[i],&w[i]);
23         }
24         memset(f,0.0,sizeof(f));
25         for(i=0;i<m;i++){
26             for(j=n;j>=c[i];j--){//比較是鑒于概率論的知識(shí)
27                 f[j]=f[j]>(1-(1-f[j-c[i]])*(1-w[i]))?f[j]:(1-(1-f[j-c[i]])*(1-w[i]));
28             }
29         }
30         double sum=f[n]*100;
31         printf("%.1lf%%\n",sum);
32     }
33     return 0;
34 }
35