[이.코.테] 그리디 (2) -- 큰 수의 법칙

 

# 배열의 수들을 M번 더하여 가장 큰 수를 만드는 법칙.
# 단, 특정 인덱스에 해당하는 수가 연속해서 K번 초과하여 더해질 수는 없음.
# 인덱스가 다른데 값이 같을 경우 서로 다른 값으로 간주함.
# N: 배열 크기, M: 숫자 더하는 횟수, K: 연속해서 더할 수 있는 횟수

# N, M, K 공백으로 구분하여 입력 받기
n, m, k = map(int, input().split())

# N개의 자연수 공백으로 구분하여 입력 받기
data = list(map(int, input().split()))

max_value = max(data)   # 가장 큰 수
data.remove(max_value)
next_max = max(data)    # 두 번째로 큰 수

result = 0
cnt = k
# 가장 큰 수를 더하는데, 연속해서 K번 더할 수는 없음
for i in range(m):
    if cnt == 0:
        # 두 번째로 큰 수를 한 번 더하기
        result += next_max
        cnt = k
    else :
        # 가장 큰 수를 k번 더하기
        result += max_value
        # 더할 때마다 1씩 빼기
        cnt -= 1

print(result)


'''
n, m, k = map(int, input().split())
data = list(map(int, input().split()))
data.sort()     # 입력받은 수들 정렬하기
first = data[n - 1]
second = data[n - 2]

# [1] 단순하게 푸는 방법

result = 0
while True:
    for i in range(k):  # 가장 큰 수 k번 더하기
        if m == 0:
            break
        result += first
        m -= 1  
    if m == 0:
        break 
    result += second
    m -= 1


# [2] 수학 공식 이용

# 가장 큰 수가 더해지는 횟수 계산
count = int(m/(k+1)) * k
count += m % (k+1)

result = 0
result += (count) * first   # 가장 큰 수 더하기
result += (m-count) * second    # 두 번째로 큰 수 더하기

print(result)

'''