Optimal Weather Report Compression

The Association for Climatological Measurement has deployed many small devices around the world. Each device observes the local weather every day, where the weather can be one of four types: Sunny, Cloudy, Rainy, or Frogs. After n days of observation, the device sends a report to the main server. Due to the bandwidth constraints, your task is to design an encoding scheme that compresses these reports into as few bits as possible.

Assume that the weather on each day is generated independently and that the probabilities for the four weather types are given as \(p_1, p_2, p_3, p_4\) (which sum to 1). In the report, every possible sequence of weather over n days (there are \(4^n\) sequences) must be encoded as a unique bit string. Moreover, to allow the server to determine where one report ends and the next begins, no encoded string can be a prefix of any other encoded string (i.e. the code must be prefix‐free).

The goal is to construct a prefix code that minimizes the expected number of bits transmitted. Using properties of Huffman coding for independent events, the optimal strategy is to construct the optimal code for a single day and repeat it for every day. In other words, if the optimal average bits for one day is \(L^* = \sum_{i=1}^{4} p_i \ell_i\) where \(\ell_i\) are the code lengths assigned to each weather type by the Huffman algorithm, then the minimum expected number of bits to encode the n-day report is:

[ E = n \cdot L^* ]

Your task is to compute this minimum expected number of bits given n and the four probabilities.

inputFormat

The input consists of two lines. The first line contains a single positive integer n (\(1 \le n \le 10^6\)), the number of days in the report. The second line contains four space‐separated real numbers \(p_1, p_2, p_3, p_4\) (each between 0 and 1, summing up to 1), representing the probabilities of the four weather types.

outputFormat

Output a single real number, representing the minimum expected number of bits needed for the report. Your answer will be accepted if it has an absolute or relative error of at most \(10^{-6}\).

sample

1
0.5 0.25 0.125 0.125

1.75