A group of friends want to buy a bouquet of flowers.  The florist wants to maximize his number of new customers and the money he makes.  To do this, he decides he'll multiply the price of each flower by the number of that customer's previously purchased flowers plus $1$.  The first flower will be original price, $(0+1)\times\text{original price}$, the next will be $(1+1)\times\text{original price}$ and so on.  

Given the size of the group of friends, the number of flowers they want to purchase and the original prices of the flowers, determine the minimum cost to purchase all of the flowers.  The number of flowers they want equals the length of the $\textbf{C}$ array.  

Example 

$c=[1,2,3,4]$ 

$k=3$   

The length of $c=4$, so they want to buy $4$ flowers total.  Each will buy one of the flowers priced $[2,3,4]$ at the original price.  Having each purchased $x=1$ flower, the first flower in the list, $c\left[\textbf{0}\right]$, will now cost $(\textit{current purchase}+\textit{previous purchases})\times c[0]=(1+1)\times1=2$.  The total cost is $2+3+4+2=11$.  

Function Description

Complete the getMinimumCost function in the editor below.   

getMinimumCost has the following parameter(s):

int c[n]: the original price of each flower
int k: the number of friends   

Returns 

- int: the minimum cost to purchase all flowers

Input Format

The first line contains two space-separated integers $n$ and $\boldsymbol{\mbox{k}}$, the number of flowers and the number of friends. 

The second line contains $n$ space-separated positive integers $c[i]$, the original price of each flower.

Constraints

$1\le n,k\le100$  
$1\leq c[i]\leq10^{6}$  
$a n swer<2^{31}$  
$0\leq i<n$

Sample Input 0
3 3
2 5 6

Sample Output 0
13

Explanation 0

There are $n=3$ flowers with costs $c=[2,5,6]$ and $k=3$ people in the group. If each person buys one flower, the total cost of prices paid is $2+5+6=13$ dollars. Thus, we print $13$ as our answer.  

Sample Input 1
3 2
2 5 6

Sample Output 1
15

Explanation 1

There are $n=3$ flowers with costs $c=[2,5,6]$ and $k=2$ people in the group. We can minimize the total purchase cost like so:

The first person purchases $2$ flowers in order of decreasing price; this means they buy the more expensive flower ($c_1=5$) first at price $p_1=(0+1)\times5=5$ dollars and the less expensive flower ($c_0=2$) second at price $p_0=(1+1)\times2=4$ dollars. 
The second person buys the most expensive flower at price $p_2=(0+1)\times6=6$ dollars. 

We then print the sum of these purchases, which is $5+4+6=15$, as our answer.

Sample Input 2
5 3
1 3 5 7 9

Sample Output 2
29

Explanation 2

The friends buy flowers for $\mbox{9}$, $7$ and $3$, $5$ and $\mbox{I}$ for a cost of $9+7+3*(1+1)+5+1*(1+1)=29$.

Source: hackerrank | Difficulty: MEDIUM
Tags: Greedy algorithms


Solutions:
(N, k) = [int(i) for i in input().split(' ')]
ci = [int(i) for i in input().split(' ')]
ci.sort()
if N < len(ci):
	N = len(ci)
(totalCount, perPerson, curRound, totalAmount) = (0, 0, 0, 0)
pFlower = len(ci) - 1
while totalCount < N:
	totalAmount += ci[pFlower] * (perPerson + 1)
	curRound += 1
	if curRound == k:
		curRound = 0
		perPerson += 1
	totalCount += 1
	pFlower -= 1
print(totalAmount)


(n, k) = [int(i) for i in input().split(' ')]
cost = [-int(i) for i in input().split(' ')]
cost = sorted(cost)
total = 0
for i in range(n):
	total -= cost[i] * (i // k + 1)
print(total)


(N, K) = input().split()
N = int(N)
K = int(K)
C = sorted([int(i) for i in input().strip().split()], reverse=True)
result = 0
p = 1
for (n, i) in enumerate(C, start=1):
	result += p * i
	if n % K == 0:
		p += 1
print(result)


NK = input()
N = int(NK.partition(' ')[0])
K = int(NK.partition(' ')[2])
prices = [int(x) for x in input().strip().split(' ')]
if K == N:
	print(sum(prices))
else:
	prices.sort()
	friends = [[] for friend in range(K)]
	for friend in friends:
		friend.append(prices.pop())
	index = 0
	while prices:
		friends[index].append(prices.pop() * (1 + len(friends[index])))
		index = (index + 1) % K
	total = 0
	for friend in friends:
		total += sum(friend)
	print(total)


x = input().split()
data = input().split()

def mergeSort(left, right):
	result = []
	if left >= right:
		return
	mid = (left + right) // 2
	mergeSort(left, mid)
	mergeSort(mid + 1, right)
	i = left
	j = mid + 1
	while i <= mid and j <= right:
		if int(data[i]) > int(data[j]):
			result.append(data[i])
			i += 1
		else:
			result.append(data[j])
			j += 1
	while i <= mid:
		result.append(data[i])
		i += 1
	while j <= right:
		result.append(data[j])
		j += 1
	i = left
	idx = 0
	while i <= right:
		data[i] = result[idx]
		idx += 1
		i += 1
N = int(x[0])
K = int(x[1])
i = 0
x = -1
total = 0
mergeSort(0, N - 1)
while i < N:
	if i % K == 0:
		x += 1
	price = (x + 1) * int(data[i])
	total += price
	i += 1
print(total)


NK = input()
N = int(NK.partition(' ')[0])
K = int(NK.partition(' ')[2])
prices = [int(x) for x in input().strip().split(' ')]
if K == N:
	print(sum(prices))
else:
	prices.sort()
	friends = [[] for friend in range(K)]
	for friend in friends:
		friend.append(prices.pop())
	index = 0
	while prices:
		friends[index].append(prices.pop() * (1 + len(friends[index])))
		index = (index + 1) % K
	total = 0
	for friend in friends:
		total += sum(friend)
	print(total)


NK = input()
N = int(NK.partition(' ')[0])
K = int(NK.partition(' ')[2])
prices = [int(x) for x in input().strip().split(' ')]
if K == N:
	print(sum(prices))
else:
	prices.sort()
	friends = [[] for friend in range(K)]
	for friend in friends:
		friend.append(prices.pop())
	index = 0
	while prices:
		friends[index].append(prices.pop() * (1 + len(friends[index])))
		index = (index + 1) % K
	total = 0
	for friend in friends:
		total += sum(friend)
	print(total)


NK = input()
N = int(NK.partition(' ')[0])
K = int(NK.partition(' ')[2])
prices = [int(x) for x in input().strip().split(' ')]
if K == N:
	print(sum(prices))
else:
	prices.sort()
	friends = [[] for friend in range(K)]
	for friend in friends:
		friend.append(prices.pop())
	index = 0
	while prices:
		friends[index].append(prices.pop() * (1 + len(friends[index])))
		index = (index + 1) % K
	total = 0
	for friend in friends:
		total += sum(friend)
	print(total)


def minCost(c, n, k):
	c.sort(key=None, reverse=True)
	flowers = [0] * k
	cost = 0
	for i in range(n):
		cost += (flowers[i % k] + 1) * c[i]
		flowers[i % k] = flowers[i % k] + 1
	return cost
[n, k] = [int(i) for i in input().strip().split()]
c = [int(i) for i in input().strip().split()]
print(minCost(c, n, k))


import sys
(N, K) = list(map(int, sys.stdin.readline().split()))
c = sorted(list(map(int, sys.stdin.readline().split())))
total = 0
purchased = 0
friends = [0] * K
while len(c) > 0:
	total += (friends[purchased % len(friends)] + 1) * c.pop()
	friends[purchased % len(friends)] += 1
	purchased += 1
print(total)


(n, k) = (int(v) for v in input().split())
c = [int(v) for v in input().split()]
total_cost = 0
c.sort(reverse=True)
for i in range(0, len(c), k):
	total_cost += sum(c[i:i + k]) * int(i / k + 1)
print(total_cost)


def price(x, f):
	return (x + 1) * f

def qs(ar):
	if len(ar) < 2:
		return ar
	start = ar[0]
	a = []
	b = []
	for e in ar[1:]:
		if e < start:
			a.append(e)
		else:
			b.append(e)
	a = qs(a)
	b = qs(b)
	ar = a + [start] + b
	return ar
read = input().split()
N = int(read[0])
K = int(read[1])
friends = []
for i in range(0, K):
	friends.append(0)
read = input().split()
flowers = []
for c in read:
	flowers.append(int(c))
money = 0
flowers = qs(flowers)
while len(flowers) > 0:
	fl = flowers[-1]
	best = 100000000000000000
	best_f = 0
	for j in range(0, len(friends)):
		p = price(friends[j], fl)
		if p < best:
			best = p
			best_f = j
	money += best
	friends[best_f] += 1
	flowers = flowers[:-1]
print(money)


curr = input().split()
N = int(curr[0])
K = int(curr[1])
C = []
C = [int(i) for i in input().split()]
C.sort()
count = 0
x = 1
pos = 0
sz = len(C) - 1
for i in range(N):
	if pos == K:
		pos = 0
		x += 1
	count += x * C[sz - i]
	pos += 1
print(count)


import sys
line1 = sys.stdin.readline()
line1Parts = line1.split(' ')
n = int(line1Parts[0])
k = int(line1Parts[1])
line2 = sys.stdin.readline()
costs = sorted([int(x) for x in line2.split(' ')], reverse=True)
minCost = 0
multiplier = 1
for i in range(0, n, k):
	subCost = multiplier * sum(costs[i:i + k])
	minCost += subCost
	multiplier += 1
print(minCost)


a = []
(n, k) = input().split()
(n, k) = [int(n), int(k)]
cost = 0
a = input().split()
a = [int(a[i]) for i in range(n)]
a.sort(reverse=True)
for i in range(n):
	cost = cost + (i // k + 1) * a[i]
print(cost)


def merge(left, right):
	result = []
	i = 0
	j = 0
	k = 0
	while i < len(left) and j < len(right):
		if left[i] <= right[j]:
			result.append(left[i])
			i += 1
		else:
			result.append(right[j])
			j += 1
		k += 1
	if i < len(left):
		result += left[i:]
	if j < len(right):
		result += right[j:]
	return result

def mergesort(lst):
	if len(lst) <= 1:
		return lst
	else:
		middle = int(len(lst) / 2)
		left = mergesort(lst[:middle])
		right = mergesort(lst[middle:])
		return merge(left, right)

def cost(array, n, k):
	a = mergesort(array)
	b1 = reversed(a)
	b = list(b1)
	cost = 0
	if n >= k:
		quotient = int(n / k)
		remainder = n % k
	else:
		return sum(array)
	for i in range(quotient):
		cost = cost + (i + 1) * sum(b[i * k:(i + 1) * k])
	cost = cost + (quotient + 1) * sum(b[quotient * k:])
	return cost
a = input()
num = [int(x) for x in a.split()]
n = num[0]
k = num[1]
string = input()
nums = [int(x) for x in string.split()]
print(cost(nums, n, k))


import sys
(n, k) = map(int, sys.stdin.readline().strip().split())
elements = list(map(int, sys.stdin.readline().strip().split()))
elements.sort(key=lambda x: -x)
ans = 0
i = 0
for w in range(1, n + 1):
	for j in range(k):
		if i == n:
			break
		ans += elements[i] * w
		i += 1
	if i == n:
		break
print(ans)


(n, k) = input().split(' ')
n = int(n)
k = int(k)
l = []
l = input().split(' ')
ans = 0
for i in range(0, n):
	l[i] = int(l[i])
	ans += l[i]
if k >= n:
	print(ans)
else:
	l.sort(reverse=1)
	ans = 0
	t = 0
	while len(l) > 0:
		for i in range(0, k):
			if len(l) > 0:
				ans += (t + 1) * l[0]
				l.remove(l[0])
		t += 1
	print(ans)


import random

def qsort(L):
	if len(L) < 2:
		return L
	pivot_element = random.choice(L)
	small = [i for i in L if i < pivot_element]
	medium = [i for i in L if i == pivot_element]
	large = [i for i in L if i > pivot_element]
	return qsort(small) + medium + qsort(large)
s = input()
I = s.split(' ')
N = int(I[0])
K = int(I[1])
strng = input()
IN = strng.split(' ')
IN2 = []
for j in IN:
	IN2.append(int(j))
IN1 = qsort(IN2)
Sum = 0
for i in range(0, N):
	Sum += int(IN1[N - 1 - i]) * (int(i / K) + 1)
print(Sum)


(N, K) = map(int, input().split())
C = list(map(int, input().split()))
C.sort()
C.reverse()
i = 0
cost = 0
while i < N:
	j = i + K
	cost += sum(C[i:j]) * (i / K + 1)
	i = j
print(int(cost))


(N, K) = map(int, input().split())
C = list(map(int, input().split()))
C.sort()
C.reverse()
i = 0
cost = 0
while i < N:
	j = i + K
	cost += sum(C[i:j]) * (i / K + 1)
	i = j
print(int(cost))


(N, K) = map(int, input().split())
C = list(map(int, input().split()))
C.sort()
C.reverse()
i = 0
cost = 0
while i < N:
	j = i + K
	cost += sum(C[i:j]) * (i / K + 1)
	i = j
print(int(cost))


(N, K) = map(int, input().split())
C = list(map(int, input().split()))
C.sort()
C.reverse()
i = 0
cost = 0
while i < N:
	j = i + K
	cost += sum(C[i:j]) * (i / K + 1)
	i = j
print(int(cost))


def main():
	(n, k) = list(map(int, input().split()))
	fs = list(map(int, input().split()))
	fs.sort(reverse=True)
	(s, m) = (0, 0)
	for i in range(0, len(fs), k):
		m += 1
		s += sum(fs[i:i + k]) * m
	print(s)
main()


import math
NK = input().split(' ')
n = int(NK[0])
k = int(NK[1])
c = []
split = input().split(' ')
result = 0
i = 0
for s in split:
	c.append(int(s))
	if n == k:
		result += int(s)
if n != k:
	c.sort(reverse=True)
	counter = 0
	a = 0
	while a < n:
		result += c[a] * (a // k + 1)
		a = a + 1
print(result)


import math

def SolveUnequal(Flowers, Friends, List, Total):
	List.sort(reverse=True)
	Holder = []
	for Each in range(Friends):
		Holder.append([])
	for K in range(len(Holder)):
		Index = K
		while Index <= len(List) - 1:
			Holder[K].append(Index)
			Index += Friends
	for K in range(len(Holder)):
		for i in range(len(Holder[K])):
			Total += int((i + 1) * List[Holder[K][i]])
	print(Total)

def SolveEqual(Flowers, Friends, List, Total):
	for Value in List:
		Total += int(Value)
	print(Total)
(N, K) = input().split()
Cost = [int(x) for x in input().split()]
if int(K) == len(Cost):
	SolveEqual(int(N), int(K), Cost, 0)
else:
	SolveUnequal(int(N), int(K), Cost, 0)


a = input().split()
n = int(a[0])
k = int(a[1])
a = input().split()
c = [int(x) for x in a]
c.sort()
c.reverse()
s = 0
i = 0
r = 0
for z in c:
	s += (i + 1) * z
	r += 1
	if r == k:
		r = 0
		i += 1
print(s)


a = input().split()
n = int(a[0])
k = int(a[1])
a = sorted([int(b) for b in input().split()])
count = 0
b = [a[len(a) - i - 1] for i in range(len(a))]
for i in range(len(b)):
	count += b[i] * (1 + i // k)
print(count)


(N, K) = input().split()
N = int(N)
K = int(K)
C = []
numbers = input()
for number in numbers.split():
	C.append(int(number))

def solution():
	C.sort(reverse=True)
	money_sum = 0
	multipler = 0
	for i in range(N):
		if i % K == 0:
			multipler += 1
		money_sum += C[i] * multipler
	return money_sum
print(solution())


(N, K) = [int(x) for x in input().split(' ')]
c = [int(x) for x in input().split(' ')]
c.sort(reverse=True)
cost = 0
for x in range(0, N // K + 1):
	cost += (x + 1) * sum(c[x * K:(x + 1) * K])
print(cost)


def purchase(x, c):
	return (x + 1) * c

def calc_cost(n, k, c):
	c_max = reversed(sorted(c))
	cost = 0
	for (x, val) in enumerate(c_max):
		x = x // k
		cost += purchase(x, val)
	return cost
a = input().strip()
a = list(map(int, a.split(' ')))
n = a[0]
k = a[1]
c = input().strip()
c = list(map(int, c.split(' ')))
print(calc_cost(n, k, c))


people = [int(i) for i in input().split()][1]
flowers = [int(i) for i in input().split()]
flowers.sort()
flowers = flowers[::-1]
s = 0
for (i, cost) in enumerate(flowers):
	s += cost * (i // people + 1)
print(s)


import itertools as it
(N, K) = map(int, input().split())
ci = list(map(int, input().split()))
bought = [0] * K
j = 0
cost = 0
ci.sort(reverse=True)
for i in it.cycle(range(K)):
	if j == N:
		break
	bought[i] += 1
	cost += bought[i] * ci[j]
	j += 1
print(cost)


def buyflowers(N, K, prices):
	if K == N:
		return sum(prices)
	else:
		prices.sort()
		listoffriends = [[] for friend in range(K)]
		for friend in listoffriends:
			friend.append(prices.pop())
		index = 0
		while prices:
			listoffriends[index].append(prices.pop() * (1 + len(listoffriends[index])))
			index = (index + 1) % K
		totalcost = 0
		for friend in listoffriends:
			totalcost += sum(friend)
		return totalcost
NK = input()
N = int(NK.split(' ')[0])
K = int(NK.split(' ')[1])
prices = [int(x) for x in input().strip().split(' ')]
print(buyflowers(N, K, prices))


(n, k) = [int(x) for x in input().split()]
flowers = [int(x) for x in input().split()]
flowers.sort(reverse=True)
sum = 0
for i in range(n):
	sum += flowers[i] * (1 + int(i / k))
print(sum)


temp = input()
temp = temp.split(' ')
N = int(temp[0])
K = int(temp[1])
temp = input()
temp = temp.split(' ')
flower = []
for x in temp:
	flower.append(int(x))
flower.sort()
flower = flower[::-1]
total = 0
count = 0
while count < len(flower):
	total += flower[count] * (count // K + 1)
	count += 1
print(total)


(nflowers, nfriends) = (int(x) for x in input().split())
prices = list(map(int, input().split()))
prices.sort(reverse=True)
to_pay = 0
for i in range(nflowers):
	x = i // nfriends
	price = (x + 1) * prices[i]
	to_pay += price
print(to_pay)


(K, N) = [int(x) for x in input().split()]
arr = sorted([int(x) for x in input().split()])
arr.reverse()
friendArr = [0] * N
for (i, j) in enumerate(arr):
	friendArr[i % N] += (i // N + 1) * j
print(sum(friendArr))


MAX = 1000000 * 101 * 50 + 1
(n, k) = [int(s) for s in input().split()]
L = [int(s) for s in input().split()]
if n == k:
	print(sum(L))
	import sys
	sys.exit(0)
L.sort(reverse=True)
friends = [(0, 0)] * k
for cost in L:
	min_cost = MAX
	chosen = -1
	for i in range(len(friends)):
		partial = cost * (friends[i][0] + 1)
		if partial < min_cost:
			min_cost = partial
			chosen = i
	assert chosen != -1
	friends[chosen] = (friends[chosen][0] + 1, friends[chosen][1] + partial)
print(sum([friend[1] for friend in friends]))


s = list(map(int, input().split(' ')))
n = s[0]
k = s[1]
c = list(map(int, input().split(' ')))
c.sort(reverse=True)
cs = 0
x = 1
for i in range(n):
	cs += (i // k + 1) * c[i]
print(cs)


import sys
raw = sys.stdin.readline().split()
numberOfFlowers = int(raw[0])
numberOfFriends = int(raw[1])
prices = []
raw = sys.stdin.readline().split()
for index in range(numberOfFlowers):
	prices.append(int(raw[index]))
prices.sort(reverse=True)
table = []
for index in range(numberOfFriends):
	table.append([])
price = 0
for (index, flower) in enumerate(prices):
	friend = index % numberOfFriends
	table[friend].append(flower)
	price += len(table[friend]) * flower
print(price)


import sys
line = sys.stdin.readline().split(' ')
(numitems, numfriends) = (int(line[0]), int(line[1]))
items = [int(x) for x in sys.stdin.readline().split(' ')]
items.sort()
items.reverse()
cost = 0
weight = 1
count = numfriends
for x in range(numitems):
	if count == 0:
		count = numfriends
		weight = weight + 1
	cost = cost + weight * items[x]
	count = count - 1
print(cost)


(n, k) = map(int, input().split())
cs = sorted(map(int, input().split()))
cs.reverse()
f = 1
c = 0
for j in range(0, n, k):
	c += f * sum(cs[j:j + k])
	f += 1
print(c)


(flower_count, buyer_count) = map(int, input().split())
prices = list(map(int, input().split()))
prices.sort(reverse=True)
total_cost = 0
for i in range(flower_count):
	total_cost += (i // buyer_count + 1) * prices[i]
print(total_cost)


(N, K) = [int(v) for v in input().split()]
c = sorted([int(v) for v in input().split()], reverse=True)
rounds = N // K + 1
result = 0
for i in range(rounds):
	start = i * K
	end = min(start + K, N)
	result += (i + 1) * sum(c[start:end])
print(result)


import sys
[N, K] = [int(X) for X in sys.stdin.readline().split()]
cs = sorted([int(X) for X in sys.stdin.readline().split()], reverse=True)
multipliers = [i // K + 1 for i in range(N)]
print(sum([i * j for (i, j) in zip(cs, multipliers)]))


import sys

def main():
	(n, k) = (int(i) for i in sys.stdin.readline().split())
	flowers = [int(i) for i in sys.stdin.readline().split()]
	flowers.sort(reverse=True)
	total = 0
	for i in range(len(flowers[::k]) + 1):
		total += (i + 1) * sum(flowers[i * k:i * k + k])
	print(total)
main()


(N, K) = list(map(int, str(input()).split()))
C = list(map(int, str(input()).split()))
C.sort()
C.reverse()
total = 0
for (i, c) in enumerate(C):
	total += (i // K + 1) * c
print(total)


import sys
import collections
(n, k) = [int(x) for x in input().split()]
ar = [int(x) for x in input().split()]

def leastCostFlowers(flowers, friends):
	flowers.sort(reverse=True)
	amounts = [0] * friends
	j = 0
	total = 0
	for flower in flowers:
		if j == friends:
			j = 0
		total += flower * (amounts[j] + 1)
		amounts[j] += 1
		j = j + 1
	return total
print(leastCostFlowers(ar, k))


(numFlowers, numPeople) = [int(x) for x in input().split()]
prices = [int(x) for x in input().split()]
assert 1 <= numFlowers
assert numPeople <= 1000000
assert len(prices) == numFlowers
cost = 0
roundz = 0
prices.sort(reverse=True)
for x in range(numFlowers):
	cost += prices[x] * (roundz + 1)
	if (x + 1) % numPeople == 0:
		roundz += 1
print(cost)


import fileinput

def get_ints_from_line(line):
	return [int(x) for x in line.split(' ')]
for line in fileinput.input():
	if fileinput.lineno() == 1:
		int_array = get_ints_from_line(line)
		N = int_array[0]
		K = int_array[1]
	else:
		int_array = get_ints_from_line(line)
		int_array.sort()
		int_array.reverse()
		current = 0
		total = 0
		index = 0
		while index < len(int_array):
			for i in range(index, index + K):
				if i < len(int_array):
					total += (current + 1) * int_array[i]
			current += 1
			index += K
print(total)


a = input().strip()
a = list(map(int, a.split(' ')))
N = a[0]
K = a[1]
b = input().strip()
b = list(map(int, b.split(' ')))
answer = 0
b.sort()
for x in range(0, len(b)):
	C = b[N - 1 - x]
	if x < K:
		answer += C
	else:
		answer += (x // K + 1) * C
print(answer)


(sN, sK) = [int(x) for x in input().split()]
N = int(sN)
K = int(sK)
C = [int(x) for x in input().split()]
C.sort(reverse=True)
vK = [0 for i in range(K)]
sumX = 0
for i in C:
	sumX += (vK[C.index(i) % K] + 1) * i
	vK[C.index(i) % K] += 1
print(sumX)


from math import floor
(N, K) = [int(e) for e in input().split()]
C = [int(e) for e in input().split()]
C.sort()
C.reverse()
cost = 0
for i in range(N):
	mul = 1 + floor(i / K)
	cost += mul * C[i]
print(cost)


[N, K] = [int(i) for i in str(input()).split()]
prices = sorted([int(j) for j in str(input()).split()], reverse=True)
customers = [0] * K
money = 0
c = 0
for f in range(N):
	money += (customers[c] + 1) * prices[f]
	customers[c] += 1
	c = (c + 1) % K
print(money)


[N, k] = [int(x) for x in input().split()]
fs = [int(x) for x in input().split()]
fs.sort(reverse=True)
i = 0
sum = 0
while len(fs) >= (i + 1) * k:
	for f in fs[k * i:k * (i + 1)]:
		sum += (i + 1) * f
	i += 1
for f in fs[k * i:]:
	sum += (i + 1) * f
print(sum)


(n, k) = map(int, input().split())
c = sorted(map(int, input().split()), reverse=True)
(answer, t) = (0, 1)
while c:
	(b, c) = (c[:k], c[k:])
	answer += t * sum(b)
	t += 1
print(answer)


import sys

def quick_sort(arr, s):
	if s == 1:
		return arr
	if s == 0:
		return []
	smaller = []
	bigger = []
	value = arr[0]
	for x in range(1, s):
		if arr[x] >= value:
			bigger.append(arr[x])
		else:
			smaller.append(arr[x])
	result = quick_sort(smaller, len(smaller)) + [value] + quick_sort(bigger, len(bigger))
	return result

def buy_flowers(ammount, friends, flower_prices):
	total_price = 0
	friends_ammount = friends
	friends = [0 for i in range(friends)]
	flower_prices = flower_prices[:ammount]
	flower_prices = flower_prices[::-1]
	for (flowers_bought, flower) in enumerate(flower_prices):
		if flowers_bought < ammount:
			total_price += flower * (1 + friends[flowers_bought % friends_ammount])
			friends[flowers_bought % friends_ammount] += 1
		else:
			break
	return total_price
(N, K) = sys.stdin.readline().strip().split()
(N, K) = (int(N), int(K))
C = sys.stdin.readline().strip().split()
C = [int(i) for i in C]
C = quick_sort(C, len(C))
print(buy_flowers(N, K, C))


N_K = input()
(N, K) = N_K.split(' ')
N = int(N)
K = int(K)
data = input()
data = data.split(' ')
for i in range(0, len(data)):
	data[i] = int(data[i])
data.sort(reverse=True)
x = 0
total = 0
for i in range(0, len(data)):
	if i % K == 0 and i > 0:
		x += 1
	total += (x + 1) * data[i]
print(total)


def get_and_return_list():
	return list(map(lambda x: int(x), input().split(' ')))
(n, k) = get_and_return_list()
flowers = get_and_return_list()
flowers.sort(reverse=True)
comp = [0 for _ in range(k)]
total = 0
for i in range(n):
	p_fl = flowers[i]
	precio = (comp[i % k] + 1) * p_fl
	total += precio
	comp[i % k] += 1
print(total)


import sys

def least_price(costs, num_friends):
	costs = reversed(sorted(costs))
	paid = [0] * num_friends
	purchases = [0] * num_friends
	for (buyer_count, cost) in enumerate(costs):
		buyer = buyer_count % num_friends
		paid[buyer] += (purchases[buyer] + 1) * cost
		purchases[buyer] = purchases[buyer] + 1
	return sum(paid)
(N, K) = sys.stdin.readline().strip().split()
K = int(K)
costs = sys.stdin.readline().strip().split()
costs = [int(c) for c in costs]
print(least_price(costs, K))


(N, K) = [int(x) for x in input().split()]
Cs = [int(x) for x in input().split()]
Cs.sort(reverse=True)
s = 0
x = -1
for (i, c) in enumerate(Cs):
	if i % K == 0:
		x += 1
	s += (x + 1) * c
print(s)


(N, K) = [int(x) for x in input().split()]
flowers = [int(x) for x in input().split()]
flowers.sort()
totalCost = 0
multiplier = 1
while flowers:
	for i in range(K):
		totalCost += flowers.pop() * multiplier
		if not flowers:
			break
	multiplier += 1
print(totalCost)


from functools import reduce
(N, K) = list(map(int, input().split()))
c = list(map(int, input().split()))
c.sort()
c.reverse()
flowers = [0] * K
cost = 0
for i in range(N):
	n = flowers[i % K]
	cost += (n + 1) * c[i]
	flowers[i % K] += 1
print(cost)


t = input().split(' ')
k = int(t[1])
n = input().split(' ')
n = [int(i) for i in n]
n.sort(reverse=True)
x = 0.0001
c = 0
for i in range(len(n)):
	c += (int(x) + 1) * int(n[i])
	x += 1 / k
print(c)


import math
numLines = 2
(N, K) = [int(num) for num in input().split(' ')]
costs = [int(price) for price in input().split(' ')]
costs.sort(reverse=True)
total_cost = 0
current_flower = 0
for costNum in range(N):
	total_cost += int(costNum / K + 1) * costs[costNum]
print(total_cost)


def popList(aloi, toPop):
	out = 0
	for i in range(toPop):
		if aloi:
			out += aloi.pop()
		else:
			break
	return out
(n, k) = [int(val) for val in input().split()]
costs = list(sorted([int(val) for val in input().split()]))
rounds = 0
out = 0
while costs:
	out += (rounds + 1) * popList(costs, k)
	rounds += 1
print(out)


def flowers(k, L):
	L.sort()
	F = [0 for i in range(k)]
	L.reverse()
	d = 0
	j = 0
	for i in L:
		if j == k:
			j = 0
		d += i * (F[j] + 1)
		F[j] += 1
		j += 1
	return d
(N, K) = str(input()).split()
L = [int(i) for i in input().split()]
print(flowers(int(K), L))


(N, K) = [int(x) for x in input().split(' ')]
v = sorted([int(x) for x in input().split(' ')])[::-1]
total = 0
for i in range(N):
	total += v[i] * (i // K + 1)
print(total)


(K, N) = map(int, input().split())
flowers = list(map(int, input().split()))
(cost, X) = (0, 0)
flowers.sort(reverse=True)
for i in range(len(flowers)):
	cost += flowers[i] * (X + 1)
	if (i + 1) % N == 0:
		X += 1
print(cost)


(N, K) = input().split()
N = int(N)
K = int(K)
arr = [int(x) for x in input().split()]
arr = sorted(arr)
rest = N
total = 0
x = 0
while rest >= 0:
	for j in range(0, K):
		rest = rest - 1
		if rest < 0:
			break
		total = total + (x + 1) * arr[N - 1 - x * K - j]
	x = x + 1
print(total)


import math
(n, k) = [int(item) for item in input().split(' ')]
c = [int(item) for item in input().split(' ')]
c.sort()
sum = 0
count = 0
for i in reversed(range(len(c))):
	multiplier = math.floor(count / k)
	count = count + 1
	sum = sum + (multiplier + 1) * c[i]
print(sum)


s = input('').split()
flowers = int(s[0])
people = int(s[1])
rate_ip = input('').split()
rate = []
for i in range(0, flowers):
	rate.append(int(rate_ip[i]))
prize = sorted(rate)[::-1]
p = people
x = 0
money = 0
for i in range(0, flowers):
	money = money + (x + 1) * prize[i]
	p -= 1
	if p == 0:
		x += 1
		p = people
print(str(money))


flowers = input().split()
numFlowers = int(flowers[0])
numBuyers = int(flowers[1])
allPrices = []
allPrices = input().split()
allPrices = [int(x) for x in allPrices]
allPrices.sort(reverse=True)
moneySpent = 0
allBuyers = []
for i in range(numBuyers):
	allBuyers.append(1)
j = 0
for i in range(numFlowers):
	moneySpent += allBuyers[j] * int(allPrices[i])
	allBuyers[j] += 1
	if j < numBuyers - 1:
		j += 1
	else:
		j = 0
print(moneySpent)


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
l.reverse()
sum1 = 0
count = 0
for i in range(n):
	sum1 = sum1 + l[i] * (count // k + 1)
	count = count + 1
print(sum1)


(n, k) = [int(c) for c in input().split()]
costs = [int(c) for c in input().split()[:n]]
costs.sort(reverse=True)
sum = 0
for i in range(n):
	sum += (int(i / k) + 1) * costs[i]
print(sum)


(_, K) = map(int, input().split())
C = sorted(map(int, input().split()), reverse=True)
X = [0 for _ in range(K)]
P = [0 for _ in range(K)]
for (i, c) in enumerate(C):
	P[i % K] += (X[i % K] + 1) * c
	X[i % K] += 1
print(sum((p for p in P)))


ins = list(map(int, input().split()))
n = ins[0]
k = ins[1]
c = list(map(int, input().split()))

def sort(arr):
	larger = []
	equal = []
	less = []
	if len(arr) > 1:
		pivot = arr[0]
		for i in range(len(arr)):
			if arr[i] > pivot:
				larger.append(arr[i])
			elif arr[i] < pivot:
				less.append(arr[i])
			else:
				equal.append(arr[i])
		return sort(larger) + equal + sort(less)
	else:
		return arr
sp = sort(c)
total = 0
for i in range(len(sp)):
	total += sp[i] * (int(i / k) + 1)
print(total)


from itertools import cycle
(N, K) = map(int, input().split())
ar = [int(x) for x in input().split()]
ar.sort(reverse=True)
friends = [int(0)] * K
i_cycle = cycle(range(K))
cost = 0
count = 0
for flower in ar:
	friend = i_cycle.__next__()
	cost += flower * (friends[friend] + 1)
	count += 1
	friends[friend] += 1
	if count == N:
		break
print(cost)


(n, k) = [int(x) for x in str(input()).split()]
c = sorted([int(x) for x in str(input()).split()])
nums = [0] * k
i = 0
result = 0
while n > 0:
	result += (nums[i] + 1) * c[n - 1]
	nums[i] += 1
	i = 0 if i == len(nums) - 1 else i + 1
	n -= 1
print(result)


inp = str(input()).split()
(N, K) = (int(inp[0]), int(inp[1]))
inp = str(input()).split()
c = [int(x) for x in inp]
c.sort()
c.reverse()
new_c = [c[K * x:K * (x + 1)] for x in range(N // K)]
new_c.append(c[len(c) - N % K:])
newer_c = [new_c[x] * (x + 1) for x in range(len(new_c))]
c = [sum(newer_c[x]) for x in range(len(newer_c))]
print(sum(c))


def solve(n, flowers):
	flowers.sort()
	total_flowers = len(flowers)
	money = 0
	buy_mult = 1
	while total_flowers > 0:
		start_i = total_flowers - n
		if total_flowers < n:
			start_i = 0
		last_f = flowers[start_i:total_flowers]
		money += sum(last_f) * buy_mult
		total_flowers = total_flowers - n
		buy_mult += 1
	return money
n_k = [int(x) for x in input().split(' ')]
flowers = [int(x) for x in input().split(' ')]
print(solve(n_k[1], flowers))


(n, k) = [int(x) for x in str(input()).split()]
c = [int(x) for x in str(input()).split()]
c.sort()
c.reverse()
total = 0
for i in range(n):
	fn = i // k
	total += (fn + 1) * c[i]
print(total)


(n, k) = map(int, input().split(' '))
prices = list(map(int, input().split(' ')))
prices.sort(reverse=True)
cost = 0
for (i, c) in enumerate(prices):
	cost += (i // k + 1) * c
print(cost)


(cases, friends) = [int(x) for x in input().split(' ')]
costs = reversed(sorted([int(x) for x in input().split(' ')]))
cost = 0
multiplier = 1
for (index, flower) in enumerate(costs):
	if index == 0 or index % friends:
		cost += multiplier * flower
	else:
		multiplier += 1
		cost += multiplier * flower
print(cost)


(n, k) = map(int, input().split())
flowers = list(map(int, input().split()))
flowers.sort(reverse=True)
cost = 0
start = 0
cycles = 0
while start < n:
	cycles += 1
	stop = min(start + k, n)
	for i in range(start, stop):
		cost += flowers[i] * cycles
	start = stop
print(cost)


(_, k) = [int(i) for i in input().split()]
cs = sorted([int(i) for i in input().split()], reverse=True)
print(sum(((i // k + 1) * c for (i, c) in enumerate(cs))))


(n, k) = [int(e) for e in input().split()]
a = sorted([int(e) for e in input().split()])
a.reverse()
s = 0
for (i, e) in enumerate(a):
	s += e * (1 + i // k)
print(s)


def tc(n, k, cs):
	cs.sort(reverse=True)
	total = 0
	for i in range(n):
		weight = i // k + 1
		total += weight * cs[i]
	print(total)
(n, k) = [int(x) for x in input().split()]
cs = [int(x) for x in input().split()]
tc(n, k, cs)


(n, k) = map(int, input().split())
c = list(map(int, input().split()))
c = sorted(c)
s = 0
for i in range(len(c)):
	mod = int(i / k)
	s += c[-1 * i - 1] * (mod + 1)
print(s)


l1 = input().split()
N = int(l1[0])
K = int(l1[1])

def makelistsameline(strnos):
	return list(map(lambda x: int(x), strnos.split()))
C = sorted(makelistsameline(input()))[::-1]
normal_cases = N // K
special_cases = N % K
C_copy = C
f_per_f = 0
total = 0

def allbuy(C, f):
	tt = 0
	for x in range(K):
		temp = (f + 1) * C[x]
		tt += temp
	return tt
for x in range(normal_cases):
	total += allbuy(C, f_per_f)
	C = C[K:]
	f_per_f += 1
for x in C:
	total += (f_per_f + 1) * x
print(total)


[N, K] = [int(i) for i in input().strip().split()]
c = [int(i) for i in input().strip().split()]
x = [1] * K
c = sorted(c, reverse=True)
totalPrice = 0
for price in c:
	minX = min(x)
	totalPrice += price * minX
	x[x.index(minX)] += 1
print(totalPrice)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = [0 for i in range(k)]
a.sort()
m = 0
while n > 0:
	m += (b[(n - 1) % k] + 1) * a[n - 1]
	b[(n - 1) % k] += 1
	n -= 1
print(m)


n = input().split()
k = int(n[1])
n = int(n[0])
coststr = input().split()
costs = []
for i in coststr:
	costs.append(int(i))
costs.sort(reverse=True)
total = 0
for i in range(int(n / k)):
	total += (i + 1) * sum(costs[:k])
	costs = costs[k:]
total += (int(n / k) + 1) * sum(costs[:])
print(total)


(N, K) = map(int, input().split())
listC = list(map(int, input().split()))
listC.sort(key=None, reverse=True)
(nPerPers, rest) = divmod(N, K)
costTot = 0
i = 0
for iPerPers in range(1, nPerPers + 1):
	for iPers in range(K):
		costTot += iPerPers * listC[i]
		i += 1
for iR in range(rest):
	costTot += (nPerPers + 1) * listC[i]
	i += 1
print(costTot)


(n, k) = [int(i) for i in input().split()]
c = sorted([int(i) for i in input().split()])[::-1]
res = 0
for b in range(n):
	res += c[b] * (b // k + 1)
print(res)


def minimumpayment(n, k, a):
	roundnum = 0
	payment = 0
	for i in range(0, n, k):
		roundnum += 1
		payment += roundnum * sum(a[i:min(n, i + k)])
	return payment
line1 = input()
(N, K) = map(int, line1.split(' '))
line2 = input()
costs = [int(cost) for cost in line2.split(' ')]
costs = sorted(costs, key=None, reverse=True)
thepayment = minimumpayment(N, K, costs)
print(thepayment)


def converter(x):
	return int(x)
firstLine = input()
secondLine = input()
N = int(firstLine.split(' ')[0])
K = int(firstLine.split(' ')[1])
ci = list(map(converter, secondLine.split(' ')))
ci.sort()
ci.reverse()
money = 0
costForK = list()
for k in range(K):
	costForK.append(1)
k = 0
while len(ci) != 0:
	money += costForK[k] * ci[0]
	costForK[k] += 1
	ci.pop(0)
	k += 1
	if k == K:
		k = 0
print(money)


(n, k) = input().strip().split(' ')
(n, k) = (int(n), int(k))
cost = sorted([int(x) for x in input().strip().split(' ')], reverse=True)
my_cost = 0
iteration = 0
while len(cost) is not 0:
	tmp = cost[:k]
	my_cost += (iteration + 1) * sum(tmp)
	cost = cost[k:]
	iteration += 1
print(my_cost)


(n, k) = map(int, input().split())
flowers = list(map(int, input().split()))
flowers.sort(reverse=True)
friends = [1 for x in range(k)]
cost = 0
for f in flowers:
	(v, i) = min(((v, i) for (i, v) in enumerate(friends)))
	cost += v * f
	friends[i] += 1
print(cost)