Campus Run Strategy

You are developing a campus running application. The application randomly generates several locations by choosing one of \(m\) different location sequences. For the \(i\)-th sequence, the minimum running distance required is \(a_i\) and the probability of obtaining this sequence is \(p_i\).

You have \(n\) chances to obtain a sequence. After obtaining a sequence, you can either start running immediately using that sequence or discard it and obtain a new sequence (if you still have remaining opportunities). If you use up all your \(n\) chances, you must start running with the last obtained sequence.

Your goal is to minimize the expected running distance. Formally, if you obtain the \(i\)-th sequence with probability \(p_i\) and if you choose to stop with it, your running distance is \(a_i\). Otherwise, you can try again to potentially get a smaller running distance.

It can be shown that the optimal expected running distance \(E(n)\) satisfies the recurrence:

\[ E(1)=\sum_{i=1}^{m}p_i\,a_i,\quad E(n)=\sum_{i=1}^{m}p_i\,\min(a_i,\;E(n-1))\ (n\ge2). \]

Output the minimum expected running distance. Your answer is considered correct if its absolute or relative error does not exceed \(10^{-4}\), i.e., if your answer is \(a\) and the jury's answer is \(b\), it is accepted when \(\frac{|a-b|}{\max(1,|b|)}\le10^{-4}\).

inputFormat

The first line contains two integers \(n\) and \(m\) (1 ≤ \(n\) ≤ 10⁵, 1 ≤ \(m\) ≤ 10⁵), representing the number of opportunities and the number of different location sequences respectively.

The second line contains \(m\) real numbers \(a_1, a_2, \ldots, a_m\) representing the minimum running distance required for each sequence.

The third line contains \(m\) real numbers \(p_1, p_2, \ldots, p_m\) representing the probability of obtaining each sequence. It is guaranteed that \(\sum_{i=1}^{m}p_i=1\).

outputFormat

Output a real number representing the minimum expected running distance. The answer is accepted if its absolute or relative error does not exceed \(10^{-4}\).

sample

1 2
10 5
0.5 0.5

7.500000