题目描述

葫芦娃的爷爷又被妖怪抓走啦！

已知妖精每一天早上都有独立的$P$的概率吃掉爷爷。

葫芦架上一共有$n$只葫芦，在第$i$天的下午，会有一个能力为$f_i$的葫芦娃诞生。

这次葫芦娃们学聪明了，他们不一定会选择一个一个去救爷爷，也有可能是某几个葫芦娃集合起来一起去救爷爷。

更明确地说，每天早上，爷爷有$P$的概率被妖精吃掉，每天下午，会有一个葫芦娃诞生，能力为$f_i$，葫芦娃们可以选择：

（1）目前还在的葫芦娃一起去救爷爷，救出来的概率是他们能力之和除以$1000$，如果超过$1000$，则一定能救出来。如果救不出来，这些葫芦娃们就也被妖怪抓走了。

（2）再等等，等下一个葫芦娃诞生再考虑救不救爷爷的事情。

葫芦娃想保命的话，可以等所有葫芦娃都诞生，再去救爷爷，可那时候爷爷大概率已经被吃掉了。

为了最大化爷爷活命的概率，葫芦娃们决定先写个代码算一算，等算出来了最大概率，再以这个策略去救爷爷。

请帮帮葫芦娃的爷爷吧！

输入格式

第一行输入两个数字$n,P$，其中$n$是正整数，$P$是一个有八位小数的实数。

第二行输入每一个$f_i$。

输出格式

输出一个数字表示答案，当你的答案与正确答案的相对误差小于$1e-8$即视为正确。

样例输入1

2 0.50000000
500 500

样例输出1

0.3125000000

样例解释1

葫芦娃们有两种选择：

（1）俩葫芦娃一起救，那么只要爷爷活够两天，就$100\%$能成功，概率是$0.5^2=0.25$。

（2）两天各救各的，第一天成功的概率：$0.5*0.5=0.25$，第二天成功的概率：$0.5*0.5*0.5*0.5=0.0625$，加一起等于$0.3125$。

显然两天各救各的比较划算。

样例输入2

2 0.01000000
500 500

样例输出2

0.9801000000

样例解释2

爷爷基本上没有被吃掉的风险，两天凑一起救就一定能成功，而分开救，即便爷爷被吃掉的概率是$0$，也有$0.5*0.5=0.25$的概率救不出来。

样例输入3

10 0.12000000
100 100 150 250 300 150 220 10 10 10

样例输出3

0.4998791498

样例解释3

除了第$4,5,6$个葫芦娃等一等以外，其他葫芦娃一出生就去救爷爷，概率用如下代码算出来可得$0.4998791498$。

cin>>n>>P;
for (int i=1;i<=n;i++) cin>>a[i];
long double now=1,ans=0,tt=0; 
//now表示爷爷活到现在的概率,tt是现在攒的葫芦娃能力值 
for (int i=1;i<=n;i++)
{
	tt+=a[i]; now*=(1-P);
	if (i!=4 && i!=5 && i!=6) //这些要等人，其他救 
	{
		ans+=now*(tt/1000); //救出来的概率
		now=now*(1-tt/1000); //这是还没救出来的概率
		tt=0; 
	} 
}
printf("%.10Lf\n",ans);

样例输入4

3 0.50000000
500 500 500

样例输出4

0.3281250000

样例解释4

葫芦娃相比样例1多了一天可以救，答案总不能还是之前的答案吧。

没有大样例

数据范围

对于30%的数据：$1\leq n\leq 10$。

对于70%的数据：$1\leq n \leq 5000$。

对于100%的数据：$1\leq n \leq 10^5，0\leq P\leq 1.0,0\leq f_i\leq 1000$。