*그리디 || 큰 수의 법칙

다양한 수로 이루어진 배열을 M번 더하여 가장 큰 수를 만든다.

단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다.

서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다.

N은 배열의 크기, M은 숫자가 더해지는 횟수, K는 연속해서 더할 수 있는 횟수.

 

• [2, 4, 5, 4, 6] 배열, M = 8, K = 3은 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5 = 46 이다.
• [3, 4, 3, 4, 3] 배열, M = 7, K = 2은 4 + 4 + 4 + 4 + 4 + 4 + 4 = 28

입력 조건

• 첫번째 줄에 N (2 <= N <= 1000), M (1 <= M <= 10000), K (1 <= K <= 10000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
• 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분하며 1 이상 10000 이하의 수로 주어진다.
• 입력으로 주어지는 K는 항상 M보다 작거나 같다.

 

---

2

4

3

5

6

M = 8 K = 3

일 경우

 

6

6

6

5

+

6

6

6

5

 

가 최선이다.

즉 일정한 규칙을 갖고 반복되는 점을 인지해야 한다.

 

---

N ,M ,K = list(map(int,input().split()))

data = list(map(int,input().split()))

data.sort(reverse=True)

count = (M//(K+1)) * K

count += M % (K+1)

MAX = count * data[0]

MAX += (M - count) * data[1]

print(MAX)