潜艇威胁

Time Limit: 3000ms

Memory Limit: 65536k

Description

有一艘潜艇进入我国海域,对我国造成威胁。潜艇可能存在n(0<n<100)个区域之中,出现在第i区域的可能为wi (0<wi <1.0)。现在派出m(0<m<1000)艘猎潜艇去搜索该潜艇,搜索行动是独立的。目标在i海域这一条件下,发现目标的概率为 pi=1-e^(-ai*xi), ai(0<ai<=1.0)表示参数, xi表示搜索该区域猎潜艇的数目。现在要做出猎潜艇的分配方案,使发现目标的概率最大,最大概率是多少?

Input

有若干测试数据,第一行为两个整数n,m,接下来n行,每行有两个数 ai,wi 。

Output

输出最大发现目标的概率。

Sample Input

4 5
1.0 0.05
1.0 0.05
1.0 0.6
1.0 0.2

Sample Output

0.743

Hint

None

Source

shiwei

提交代码