에너지 관리

성관이는 앞으로 $N$일 동안 하루에 하나씩 일정을 잡아 두었다. 그런데 그 일을 모두 해내기에는 에너지가 모자랄까 봐 걱정이다.

첫날 성관이는 에너지 $E$로 하루를 시작한다. 그는 하루에 원하는 만큼 에너지를 쓸 수 있다. 하루가 끝나면 에너지를 $R$만큼 회복하지만, 에너지의 총량은 언제나 $E$를 넘지 않는다. 즉, 어느 날 에너지가 $a$만큼 남았다면 다음 날은 $\min(E, a+R)$의 에너지로 하루를 시작한다.

에너지를 많이 쓸수록 그날의 일을 잘 해낸다. 날마다 일의 중요도가 다르므로, 성관이는 더 중요한 일에 에너지를 더 써서 최대한 효율적으로 에너지를 쓰려고 한다. $i$번째 날에 맡은 일의 중요도가 $c_i$이고 그날 쓴 에너지가 $e_i$일 때, $c_1e_1 + c_2e_2 + \cdots + c_ne_n$의 값을 최대로 하는 에너지 배분을 구하시오.

첫째 줄에 $E$, $R$, $N$이 주어진다. ($1 \le E \le 10^7$, $1 \le R \le 10^7$, $1 \le N \le 10^4$)

둘째 줄에 자연수 $N$개가 주어진다. $i$번째 수가 $c_i$이다. ($1 \le c_i \le 10^7$)

$c_1e_1 + c_2e_2 + \cdots + c_ne_n$의 최댓값을 출력한다.