1026:girl friend!

Time/Memory Limit:1000 MS/32768 K
Submitted: 198 Accepted: 44

 Problem Description

money999很早就想有个女朋友,以前他没钱不敢交女朋友,但是现在他有了点钱,于是便去交女朋友了。要交任何一个女朋友,money999都要花费一定的信息费,这可是很大的开销。money999总共只攒了n万RMB。他将在m个女人中选择若干的(当然要在他的经济承受范围内)。每个女人都有不同的信息费用w(万RMB),并且money999估计了他交到这个女朋友的可能性p。不同女人之间是否成为他的女朋友不会互相影响。Girl I am coming !! ,他大叫一声。我们帮他计算一下,他可以交到至少一个女朋友的最大概率。(他选择了多个女人,得到任意一个女人都可以)。

 Input

输入有若干组数据,每组数据的第一行有两个正整数n,m(0<=n<=1000,0<=m<=1000),n表示money999手上有n万RMB,
后面有m行,每行有两个数据vi(整型),pi(实型)分别表示第i个女人的信息费用和可能成为女朋友的概率,当n和m同时为0的时候输入结束。

 Output

每组数据都对应一个输出,占一行,表示money999可能得到至少一个女朋友的最大概率。用百分数表示,精确到小数点后一位。

 Sample Input

2 3
7 0.1
4 0.2
1 0.4
0 0

 Sample Output

40.0%

 Author

yaonie

 Recommend

zh