您受雇于气候测量协会，这是一个致力于长期追踪全球天气趋势的科学组织。当然，这并非易事。他们在世界各地部署了许多小型设备，旨在定期测量当地的天气状况。这些设备价格低廉，功能有限。它们每天观测四种标准天气类型中的一种：晴天（Sunny）、多云（Cloudy）、雨天（Rainy）或青蛙（Frogs）。在完成 $n$ 次观测后，结果会被报告给主服务器进行分析。然而，海量的设备导致可用通信带宽过载。协会需要您的帮助，想出一种将这些报告压缩成更少比特的方法。

对于特定设备的位置，您可以假设每天的天气是一个独立的随机事件，并且您已知四种可能天气类型的预测概率。设备生成的每一种 $4^n$ 种可能的天气报告都必须编码为一个唯一的比特序列，且任何序列都不能是其他序列的前缀（这是一个重要的属性，否则服务器将无法知道每个序列何时结束）。目标是使用一种能使传输比特的期望数量最小化的编码方式。

输入格式

输入的第一行包含一个整数 $1 \le n \le 20$，表示每份报告包含的观测次数。第二行包含四个正浮点数 $p_{\text{sunny}}, p_{\text{cloudy}}, p_{\text{rainy}}$ 和 $p_{\text{frogs}}$，分别代表相应天气的概率。这些概率小数点后最多有 6 位数字，且总和为 1。

输出格式

输出报告编码的最小期望比特数，要求绝对误差或相对误差不超过 $10^{-4}$。

样例

输入格式 1

2
0.9 0.049999 0.05 0.000001

输出格式 1

1.457510

输入格式 2

20
0.25 0.25 0.25 0.25

输出格式 2

40.000000