시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 8 5 5 62.500%

문제

성관이는 앞으로 N일 동안 아주 바쁜 시간을 보낼 계획이다. 그는 모든 날짜에 대해 하나씩의 일정을 잡아 두었다. 하지만, 그는 그 모든 일에 사용할 에너지가 부족할 까봐 걱정이 되었다.

첫 날에, 성관이는 총 E의 에너지를 갖고 하루를 시작한다. 그는 각 날짜에 원하는 만큼의 에너지를 사용할 수 있다. 하루가 끝나면, 성관이는 총 R의 에너지를 회복한다. 하지만, 에너지의 총량은 언제나 E를 넘지 않는다. 즉, 전날 남은 에너지가 총 a 였다면, 다음날은 min(E, a+R)의 에너지를 갖고 시작하게 된다.

에너지를 많이 사용할수록, 그 날의 일을 성공적으로 수행할 수 있다. 각 날마다 배정된 일의 중요도는 모두 다르기 때문에, 성관이는 더 중요한 일에 더 많은 에너지를 사용하여, 최대한 효율적으로 에너지를 사용하고 싶어한다. i번째 날에 배정된 일의 중요도가 ci, 그 날 사용한 에너지가 ei

라고 할 때, c1e1 + c2e2 + … + cnen의 값을 최대로 하는 에너지의 배분을 구하시오.

입력

첫 번째 줄에는 E, R, N이 주어진다. (1 ≤ E ≤ 107, 1 ≤ R ≤ 107, 1 ≤ N ≤ 104)

다음 줄에는 N개의 자연수가 주어진다. i번째 수는 ci를 의미한다. (1 ≤ ci ≤ 107)

출력

c1e1 + c2e2 + … + cnen의 최댓값을 출력한다.

예제 입력 1

5 2 2
2 1

예제 출력 1

12

예제 입력 2

5 2 2
1 2

예제 출력 2

12

예제 입력 3

3 3 4
4 1 3 5

예제 출력 3

39

힌트

예제 1에서는 첫 날 5, 둘째 날 2의 에너지를 사용하면 된다.

예제 2에서는 첫 날 2, 둘째 날 5의 에너지를 사용하면 된다.

예제 3에서는 모든 날에 3씩의 에너지를 사용하면 된다.