hdu 1203 I NEED A OFFER!

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

int main()
{
    int n,m,i,j,w[10000+5];
    double k[10000+5],dp[10000+5];
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0) break;

        for(i=0;i<m;i++)
        {
            scanf("%d%lf",&w[i],&k[i]);
            k[i]=1-k[i];
        }

        for(i=0;i<=n;i++)
            dp[i]=1;

        for(i=0;i<m;i++)
        {
            for(j=n;j>=w[i];j--)
            {
                dp[j]=min(dp[j],dp[j-w[i]]*k[i]);
            }
        }

        dp[n]=1-dp[n];
        dp[n]=dp[n]*100;
        printf("%.1f%%\n",dp[n]);
    }
    return 0;
}