Energy Management

Seonggwan has one task scheduled on each of the next $N$ days. He is worried that he does not have enough energy for all of them.

On the first day Seonggwan starts with $E$ energy. He can spend as much energy as he wants on a day. At the end of a day he recovers $R$ energy, but his total energy never goes above $E$. That is, if $a$ energy is left at the end of a day, he starts the next day with $\min(E, a+R)$ energy.

The more energy he spends on a day, the better that day's task goes. The tasks differ in importance, so Seonggwan wants to spend more energy on the more important ones and use his energy as efficiently as possible. The task on day $i$ has importance $c_i$ and he spends $e_i$ energy that day. Find the distribution of energy that maximizes $c_1e_1 + c_2e_2 + \cdots + c_ne_n$.

The first line contains $E$, $R$, and $N$. ($1 \le E \le 10^7$, $1 \le R \le 10^7$, $1 \le N \le 10^4$)

The second line contains $N$ natural numbers. The $i$-th number is $c_i$. ($1 \le c_i \le 10^7$)

Print the maximum value of $c_1e_1 + c_2e_2 + \cdots + c_ne_n$.