Background

And I promise you, everything will end in a grand, theatrical trial...
Spin a little, jump lightly, and then comes the curtain call of the "sinner".

Problem Description

Define a function $a(x)$ as the sum of distinct prime factors of the natural number $x$.

If $x=\prod\limits_{p_i\in\mathbb{P}}p_i^{d_i}$, then $a(x)=\sum\limits_{p_i\in \mathbb{P}}p_i\times[d_i\ge1]$, where $\mathbb{P}$ is the set of primes, and $a(1)=0$.

Starting from the first day of her birth, Furina has had an expectation value $m_1$.

Before the final trial arrives, every day she chooses to sort out her feelings. The method is as follows:

Suppose today is day $i$. Furina sets today's expectation value $m_i$ to $\max\{\dfrac{m_j}{a(\operatorname{lcm}(w_i,w_j))+a(\gcd(w_i,w_j))}+k\}$, where $2\le i\le n$, $1\le j<i$, and $k$ is the expectation value gained from watching the trial.

Please compute $\sum\limits_{i=1}^n m_i$.

Input Format

The first line contains three integers $n,m_1,k$, representing the number of days until the final trial (including the first day), the expectation value on the first day, and the expectation value gained from watching the trial.

The second line contains $n$ integers representing $w_1,w_2,w_3,\cdots,w_n$.

Output Format

Output one real number in one line representing $\sum\limits_{i=1}^n m_i$. Your answer is considered correct if the absolute error compared with the correct answer does not exceed $10^{-6}$.

4 4 7
7 10 16 8

28.047619

Hint

Sample Explanation

The expectation values for these $4$ days are $4,7.285714,7.809524,8.952381$.

Constraints

For $100\%$ of the testdata, $1\le n\le182376$, $1\le m_1\le10^7$, $0\le k\le10^6$, $2\le w_i\le182376$.

The testdata for this problem may be a bit weak. You are welcome to provide hacks for incorrect solutions.

Translated by ChatGPT 5