HDU 1203 I NEED A OFFER!

import java.text.DecimalFormat;
import java.util.Scanner;

public class Main {

    /**
     * @param args
     */
    public static void main(String[] args) {
        
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            if(n==m&&n==0) {
                return;
            }
            
            int weight[]=new int[m];
            float ratio[]=new float[m];
            float value[]=new float[n+1];            
            
            for(int i=0;i<=n;i++){
                value[i]=1.0f;      //开始时将没有offer的最小概率都定为1
            }
            for(int i=0;i<m;i++){
                weight[i]=scanner.nextInt();        //申请费用
                ratio[i]=1-scanner.nextFloat();     //得不到offer的概率
            }
            for(int i=0;i<m;i++){
                for(int j=n;j>=weight[i];j--){
                    value[j]=Math.min(value[j], value[j-weight[i]]*ratio[i]);
                }
            }
            System.out.println(new DecimalFormat("0.0").format((1.0-value[n])*100)+"%");
//            System.out.printf("%.1f%%\n",(1-value[n])*100);
            
        }
    }

}