There are $n$ emotes in very popular digital collectible card game (the game is pretty famous so we won't say its name). The $i$-th emote increases the opponent's happiness by $a_i$ units (we all know that emotes in this game are used to make opponents happy).

You have time to use some emotes only $m$ times. You are allowed to use any emotion once, more than once, or not use it at all. The only restriction is that you cannot use the same emote more than $k$ times in a row (otherwise the opponent will think that you're trolling him).

Note that two emotes $i$ and $j$ ($i \ne j$) such that $a_i = a_j$ are considered different.

You have to make your opponent as happy as possible. Find the maximum possible opponent's happiness.


-----Input-----

The first line of the input contains three integers $n, m$ and $k$ ($2 \le n \le 2 \cdot 10^5$, $1 \le k \le m \le 2 \cdot 10^9$) — the number of emotes, the number of times you can use emotes and the maximum number of times you may use the same emote in a row.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is value of the happiness of the $i$-th emote.


-----Output-----

Print one integer — the maximum opponent's happiness if you use emotes in a way satisfying the problem statement.


-----Examples-----
Input
6 9 2
1 3 3 7 4 2

Output
54

Input
3 1000000000 1
1000000000 987654321 1000000000

Output
1000000000000000000



-----Note-----

In the first example you may use emotes in the following sequence: $4, 4, 5, 4, 4, 5, 4, 4, 5$.

Difficulty: interview

Starter code:

Solutions:
n,m,k = map(int,input().split())
a = list(map(int,input().split()))

a = sorted(a)
b1 = a[-1]
b2 = a[-2]

k+=1
total = m//k
score = 0
score += (m%k) * b1
score += b1 * (total*(k-1))
score += b2 * total
print (score)

ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(mi())

n, m, k = mi()
a = li()
mx = max(a)
mi = a.index(mx)
mx2 = max(a[:mi] + a[mi+1:])

rep = m // (k + 1)
ans = rep * (k * mx + mx2)

rem = m % (k + 1)
ans += rem * mx

print(ans)

n,m,k = list(map(int,input().split()))
A = sorted([int(x) for x in input().split()])
m1 = A[-1]
m2 = A[-2]
print(m//(k+1) * (m1*k + m2) + m%(k+1) * m1 )


n, m, k = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a, reverse=True)
s = m // (k + 1)
mod = m % (k + 1)
print(s * (a[0] * k + a[1]) + mod * a[0])

n, m, k = list(map(int, input().split()))
A = sorted(map(int, input().split()))
a, b = A[-1], A[-2]
time = m // (k + 1)
ans = time * (a * k + b)
print(ans + a * (m % (k + 1)))


def mi():
    return list(map(int, input().split()))
'''
6 9 2
1 3 3 7 4 2
'''
n,m,k = mi()
a = list(mi())
a.sort(reverse=True)
t = k+1
nop = m//t
rem = m%t
print(nop*(k*a[0]+a[1])+rem*a[0])


n,m,k=list(map(int,input().split()))
a=list(map(int,input().split()))

a.sort()
k1=a[-1]
k2 = a[-2]
x = m//(k+1)
ans = k2*x+(m-x)*k1
print(ans)


n,m,k=map(int,input().split())
arr=list(map(int,input().split()))
arr.sort()
count=m//(k+1)
ans=arr[-1]*count*k
ans+=(arr[-2])*count
ans+=arr[-1]*(m%(k+1))
print(ans)

n,m,k=list(map(int,input().split()))
a=[int(s) for s in input().split()]
a.sort()
ans=m//(k+1)*(a[-1]*k+a[-2])
ans+=m%(k+1)*a[-1]
print(ans)
    


n, m ,k = map(int, input().split())

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

mx1 = mx2 = 0
for i in range(n):
    if a[i] > mx1:
        mx2 = mx1
        mx1 = a[i]
    elif a[i] > mx2:
        mx2 = a[i]

t = m // (k+1)
ans = t*k*mx1 + t*mx2

ans += (m % (k+1))*mx1
print(ans)

#	!/usr/bin/env python3
#	coding: UTF-8
#	Modified: <18/Feb/2019 09:19:08 PM>


#	✪ H4WK3yE乡
#	Mohd. Farhan Tahir
#	Indian Institute Of Information Technology (IIIT),Gwalior

#	Question Link
#
#

# ///==========Libraries, Constants and Functions=============///


import sys

inf = float("inf")
mod = 1000000007


def get_array(): return list(map(int, sys.stdin.readline().split()))


def get_ints(): return list(map(int, sys.stdin.readline().split()))


def input(): return sys.stdin.readline()

# ///==========MAIN=============///


def main():
    n, m, k = get_ints()
    arr = get_array()
    arr.sort()
    if m <= k:
        print(arr[-1] * m)
        return
    x = arr[-1] * k + arr[-2]
    p = m // (k + 1)
    ans = x * p
    p = m % (k + 1)
    ans += (arr[-1] * p)
    print(ans)


def __starting_point():
    main()

__starting_point()

n,m,k = [int(s) for s in input().split()]
array = [int(s) for s in input().split()]
array = sorted(array,reverse = True)
first = array[0]
second = array[1]
#print(array)
res = (first * k + second) * (m // (k + 1)) + first * (m % (k + 1))
print(res)


#      
import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

isdebug = False
try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        #print(*args, **kwargs, file=sys.stderr)
        # in python 3.4 **kwargs is invalid???
        print(*args,  file=sys.stderr)
    dprint('debug mode')
    isdebug = True
except Exception:
    def dprint(*args, **kwargs):
        pass



inId = 0
outId = 0
if not isdebug:
    inId = 0
    outId = 0
if inId>0:
    dprint('use input', inId)
    try:
        f = open('input'+ str(inId) + '.txt', 'r')
        sys.stdin = f #标准输出重定向至文件
    except Exception:
        dprint('invalid input file')
if outId>0:
    dprint('use output', outId)
    try:
        f = open('stdout'+ str(outId) + '.txt', 'w')
        sys.stdout = f #标准输出重定向至文件
    except Exception:
        dprint('invalid output file')
        
    atexit.register(lambda :sys.stdout.close())     #idle 中不会执行 atexit
    
N, M, K = getIntList()
#print(N)
za  = getIntList()
dprint(za)
za.sort()

a = za[-1]
b = za[-2]

r = 0

t = M //(K+1)

r = t* ( a*K + b)
r += M%(K+1) * a


print(r)



n,m,k=list(map(int,input().split()))
A=list(map(int,input().split()))
A.sort(reverse=True)

M1=A[0]
M2=A[1]

print(M2*(m//(k+1))+M1*(m-(m//(k+1))))


N, M, K = map(int, input().split())
A = [int(a) for a in input().split()]
A = sorted(A)

m1 = A[-1]
m2 = A[-2]

a = M // (K+1)
b = M % (K+1)

print(a*(m1*K+m2)+m1*b)

import io, sys, atexit, os


import math as ma
from decimal import Decimal as dec
from itertools import permutations


def li ():
	return list (map (int, input ().split ()))


def num ():
	return map (int, input ().split ())


def nu ():
	return int (input ())


def find_gcd ( x, y ):
	while (y):
		x, y = y, x % y
	return x


def solve ():
	t = 1
	for it in range (t):
		n,m,k=num()
		a=li()
		a.sort()
		hh=a[n-1]
		h2=a[n-2]
		op=m//(k+1)
		po=m%(k+1)
		ans=op*k*hh+op*h2+po*hh
		print(ans)



def __starting_point():
	solve ()
__starting_point()

n, m, k = list(map(int, input().split()))
a = list(sorted(map(int, input().split())))
x = a[-1]
y = a[-2]
b = int(m / (k + 1))
print(b * y + (m - b) * x)


n, m, k = list(map(int, input().split()))
a = sorted(list(map(int, input().split())))
u, v = a[-2], a[-1]

print(m // (k + 1) * (v * k + u) + m % (k + 1) * v)


n, m, k = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
if m < k:
    print(A[0] * m)
else:
    k += 1
    print(A[0] * (m - m // k) + A[1] * (m // k))

import heapq

_, m, k = list(map(int, input().split()))
a, b = heapq.nlargest(2, list(map(int, input().split())))
print(a * m - m // (k + 1) * (a - b))


import heapq

n, m, k = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]

a, b = heapq.nlargest(2, arr)

nb = m // (k+1)
na = m - nb

h = na*a + nb*b
print(h)



n,m,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
r=m//(k+1)
ans=a[-1]*(r*k+(m%(k+1)))+a[-2]*r
print(ans)

import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

n, m, k = mints()
a = list(mints())
a.sort()
b = a[-1]
c = a[-2]
z = m//(k+1)
print((m-z)*b+c*z)

n,m,k=map(int,input().split())
a=list(map(int,input().split()))
mx,mxx=0,0
for i in a:
    if i>=mx:
        mxx=mx
        mx=i
    elif i>mxx:
        mxx=i
if k==m:print(mx*m)
else:
    x=m//(k+1)
    ans=x*(mx*k+mxx)+(m-(k+1)*x)*mx
    print(ans)