In a candy store, there are N different types of candies available and the prices of all the N different types of candies are provided to you.
You are now provided with an attractive offer.
For every candy you buy from the store and get at most K other candies ( all are different types ) for free.
Now you have to answer two questions. Firstly, you have to find what is the minimum amount of money you have to spend to buy all the N different candies. Secondly, you have to find what is the maximum amount of money you have to spend to buy all the N different candies.
In both the cases you must utilize the offer i.e. you buy one candy and get K other candies for free.
Example 1:
Input:
N = 4
K = 2
candies[] = {3 2 1 4}
Output:
3 7
Explanation:
As according to the offer if you buy 
one candy you can take at most two 
more for free. So in the first case, 
you buy the candy which costs 1 and 
takes candies worth 3 and 4 for free, 
also you buy candy worth 2 as well.
So min cost : 1+2 =3.
In the second case, you can buy the 
candy which costs 4 and takes candies 
worth 1 and 2 for free, also you need 
to buy candy worth 3 as well. 
So max cost : 3+4 =7.
Example 2:
Input: 
N = 5
K = 4
candies[] = {3 2 1 4 5}
Output: 
1 5
Explanation:
For minimimum cost buy the candy with
the cost 1 and get all the other candies
for free.
For maximum cost buy the candy with
the cost 5 and get all other candies
for free.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function candyStore() which takes the array candies[], its size N and an integer K as input parameters and returns the minimum amount and maximum amount of money to buy all candies according to the offer.
Expected Time Complexity: O(NLogN)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 100000
 0 <= K <= N-1
1 <= candies[i] <= 10000

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Greedy algorithms

Starter code: #User function Template for python3



class Solution:



    def candyStore(self, candies,N,K):

        # code here

Solutions:
class Solution:

	def candyStore(self, candies, N, K):
		candies = sorted(candies)
		(i, j) = (0, N)
		mn = 0
		while i < j:
			mn += candies[i]
			j -= K
			i += 1
		(i, j) = (-1, N - 1)
		mx = 0
		while i < j:
			mx += candies[j]
			i += K
			j -= 1
		return [mn, mx]


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		minimum_amount = 0
		maximum_amount = 0
		i = 0
		j = N - 1
		while i <= j:
			minimum_amount += candies[i]
			i += 1
			j -= K
		i = N - 1
		j = 0
		while i >= j:
			maximum_amount += candies[i]
			i -= 1
			j += K
		return (minimum_amount, maximum_amount)


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		c = 1 + N // (K + 1) if N % (K + 1) != 0 else N // (K + 1)
		(MIN, MAX) = (0, 0)
		for i in range(c):
			MIN += candies[i]
			MAX += candies[N - i - 1]
		return (MIN, MAX)


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		mini = 0
		(i, j) = (0, N - 1)
		while i <= j:
			mini += candies[i]
			i += 1
			j -= K
		maxi = 0
		(i, j) = (0, N - 1)
		while i <= j:
			maxi += candies[j]
			i += K
			j -= 1
		return (mini, maxi)


class Solution:

	def candyStore(self, c, N, K):
		c.sort()
		l = []
		i = 0
		j = N - 1
		mi = 0
		ma = 0
		while i <= j:
			mi += c[i]
			j -= K
			i += 1
		i = 0
		j = N - 1
		while i <= j:
			ma += c[j]
			j -= 1
			i += K
		l.append(mi)
		l.append(ma)
		return l


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		i = 0
		j = N - 1
		mini_cost = 0
		while i <= j:
			mini_cost = mini_cost + candies[i]
			i = i + 1
			j = j - K
		maxi_cost = 0
		i = 0
		j = N - 1
		while i <= j:
			maxi_cost = maxi_cost + candies[j]
			j = j - 1
			i = i + K
		return [mini_cost, maxi_cost]


class Solution:

	def candyStore(self, candies, n, k):
		candies.sort()
		buy = 0
		free = n - 1
		mini = 0
		while buy <= free:
			mini += candies[buy]
			buy += 1
			free -= k
		buy = n - 1
		free = 0
		maxi = 0
		while buy >= free:
			maxi += candies[buy]
			free += k
			buy -= 1
		ans = []
		ans.append(mini)
		ans.append(maxi)
		return ans


class Solution:

	def candyStore(self, candies, N, K):
		can = 0
		total = 0
		i = 0
		candies.sort()
		while total < N:
			can += candies[i]
			total += K + 1
			i += 1
		j = -1
		p = 0
		mtotal = 0
		while mtotal < N:
			p += candies[j]
			mtotal += K + 1
			j -= 1
		return (can, p)


class Solution:

	def candyStore(self, candies, N, K):
		result = []
		candies.sort()
		min_cost = 0
		start = 0
		end = N - 1
		while start <= end:
			min_cost += candies[start]
			start += 1
			end -= K
		result.append(min_cost)
		max_cost = 0
		start = N - 1
		end = 0
		while start >= end:
			max_cost += candies[start]
			start -= 1
			end += K
		result.append(max_cost)
		return result


def findmin(candies, N, K, l):
	res = 0
	i = 0
	candies.sort()
	while i < N:
		res += candies[i]
		N -= K
		i += 1
	l.append(res)

def findmax(candies, N, K, l):
	r = 0
	index = 0
	i = N - 1
	candies.sort()
	while i >= index:
		r += candies[i]
		index += K
		i -= 1
	l.append(r)

class Solution:

	def candyStore(self, candies, N, K):
		l = []
		findmin(candies, N, K, l)
		findmax(candies, N, K, l)
		return l


class Solution:

	def candyStore(self, candies, N, K):
		(i, j, mi, ma) = (0, N - 1, 0, 0)
		candies.sort()
		while i <= j:
			mi += candies[i]
			i += 1
			j -= K
		candies.sort(reverse=True)
		(i, j) = (0, N - 1)
		while i <= j:
			ma += candies[i]
			i += 1
			j -= K
		return [mi, ma]


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		if K > 0:
			return [self.getVal(candies, K), self.getVal(candies[::-1], K)]
		return [sum(candies), sum(candies)]

	def getVal(self, candies, K):
		(start, end) = (0, len(candies))
		total = 0
		while start < end:
			total += candies[start]
			start += 1
			end -= K
		return total


class Solution:

	def candyStore(self, candies, n, k):
		candies = sorted(candies)
		target = len(candies)
		no = 0
		min_amount = 0
		max_amount = 0
		index = 0
		while no < target:
			min_amount = min_amount + candies[index]
			max_amount = max_amount + candies[-(index + 1)]
			no = no + k + 1
			index = index + 1
		return (min_amount, max_amount)


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		top = N // (K + 1)
		if N % (K + 1) != 0:
			top = top + 1
		return (sum(candies[:top]), sum(candies[-top:]))


class Solution:

	def candyStore(self, candies, N, K):
		l = []
		i = 0
		j = N - 1
		cost = 0
		candies.sort()
		while i <= j:
			cost += candies[i]
			i += 1
			j -= K
		l.append(cost)
		i = 0
		j = N - 1
		cost = 0
		candies.sort(reverse=True)
		while i <= j:
			cost += candies[i]
			i += 1
			j -= K
		l.append(cost)
		return l


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		c = N // (K + 1)
		if N % (K + 1) != 0:
			c += 1
		min = 0
		max = 0
		i = 0
		j = N - 1
		for k in range(c):
			min += candies[i]
			i += 1
			max += candies[j]
			j -= 1
		return [min, max]


from math import ceil

class Solution:

	def candyStore(self, candies, N, K):
		candies_to_buy = ceil(N / (K + 1))
		candies.sort()
		return [sum(candies[:candies_to_buy]), sum(candies[N - candies_to_buy:])]


import heapq

class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		mini = 0
		buy = 0
		free = N - 1
		while buy <= free:
			mini += candies[buy]
			free = free - K
			buy += 1
		maxi = 0
		buy = N - 1
		free = 0
		while free <= buy:
			maxi += candies[buy]
			free = free + K
			buy -= 1
		return [mini, maxi]


class Solution:

	def candyStore(self, candies, N, k):
		a = sorted(candies, reverse=True)
		candies.sort()
		i = 0
		j = N
		sumi = 0
		tumi = 0
		while i < j:
			sumi += candies[i]
			tumi += a[i]
			i += 1
			j -= k
		return [sumi, tumi]


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		(max_a, min_a) = (0, 0)
		i = 0
		j = N - 1
		while i <= j:
			min_a += candies[i]
			i += 1
			j -= K
		i = 0
		j = N - 1
		while i <= j:
			max_a += candies[j]
			i += K
			j -= 1
		return [min_a, max_a]


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		m = 0
		ma = 0
		j = len(candies) - 1
		i = 0
		while i <= j:
			m = m + candies[i]
			j = j - K
			i += 1
		j = len(candies) - 1
		i = 0
		while i <= j:
			ma = ma + candies[j]
			i = i + K
			j -= 1
		return (m, ma)


class Solution:

	def candyStore(self, candies, N, K):
		if K == 0:
			return (sum(candies), sum(candies))
		candies.sort()
		i = 0
		j = N
		mn = 0
		mx = 0
		while i < j:
			mn += candies[i]
			i += 1
			j -= K
		i = -1
		j = N - 1
		while i < j:
			mx += candies[j]
			j -= 1
			i += K
		return (mn, mx)


class Solution:

	def candyStore(self, candies, N, K):
		i = 0
		j = N - 1
		candies.sort()
		min1 = 0
		max1 = 0
		while i <= j:
			min1 += candies[i]
			j -= K
			i += 1
		i = 0
		j = N - 1
		while i <= j:
			max1 += candies[j]
			i += K
			j -= 1
		return [min1, max1]


class Solution:

	def candyStore(self, candies, N, k):
		j = N - 1
		i = 0
		candies.sort()
		price_min = 0
		while i <= j:
			price_min += candies[i]
			target = k
			while target > 0 and j >= 0:
				j -= 1
				target -= 1
			i += 1
		j = N - 1
		i = 0
		price_max = 0
		while j >= i:
			price_max += candies[j]
			target = k
			while target > 0 and i < N:
				i += 1
				target -= 1
			j -= 1
		return [price_min, price_max]


import heapq

class Solution:

	def candyStore(self, candies, N, K):
		if K == 0:
			return [sum(candies), sum(candies)]
		heapq.heapify(candies)
		p = 0
		i = 0
		sum1 = 0
		while i + p < N:
			r = heapq.heappop(candies)
			sum1 += r
			p += K
			i += 1
		while i < len(candies):
			heapq.heappop(candies)
		if K == 1 and N % 2 != 0:
			return [sum1, sum(candies) + r]
		else:
			return [sum1, sum(candies)]


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		for_max = candies[:]
		min = 0
		max = 0
		while len(for_max) > 0:
			min += for_max.pop(0)
			for _ in range(K):
				if len(for_max) > 0:
					for_max.pop()
		while len(candies) > 0:
			max += candies.pop()
			for _ in range(K):
				if len(candies) > 0:
					candies.pop(0)
		return (min, max)


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		ans = []
		mini = 0
		i = 0
		j = N - 1
		while i <= j:
			mini += candies[i]
			i += 1
			j -= K
		ans.append(mini)
		candies.sort(reverse=True)
		i = 0
		j = N - 1
		maxi = 0
		while i <= j:
			maxi += candies[i]
			i += 1
			j -= K
		ans.append(maxi)
		return ans


class Solution:

	def candyStore(self, candies, N, K):
		(min, max) = (0, 0)
		(i, j) = (0, N - 1)
		candies.sort()
		while i <= j:
			min += candies[i]
			j -= K
			i += 1
		(i, j) = (0, N - 1)
		while i <= j:
			max += candies[j]
			j -= 1
			i += K
		return [min, max]


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		ans = []
		min = 0
		i = 0
		j = N - 1
		while i <= j:
			min += candies[i]
			i += 1
			j -= K
		ans.append(min)
		candies.sort(reverse=True)
		i = 0
		j = N - 1
		max = 0
		while i <= j:
			max += candies[i]
			i += 1
			j -= K
		ans.append(max)
		return ans


class Solution:

	def candyStore(self, c, N, K):
		res = []
		c.sort()
		sum = 0
		m = 0
		n = N - 1
		i = N - 1
		min_sum = 0
		max_sum = 0
		while m <= i:
			min_sum += c[m]
			m = m + 1
			max_sum += c[n]
			n = n - 1
			i = i - K
		res.append(min_sum)
		res.append(max_sum)
		return res


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		if K == 0:
			return (sum(candies), sum(candies))
		i = 0
		j = N
		ans_min = 0
		ans_max = 0
		while i < j:
			ans_min += candies[i]
			i += 1
			j -= K
		i = -1
		j = N - 1
		while i < j:
			ans_max += candies[j]
			i += K
			j -= 1
		return (ans_min, ans_max)


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		ans = []
		minimum = 0
		i = 0
		j = N - 1
		while i <= j:
			minimum += candies[i]
			i += 1
			j -= K
		ans.append(minimum)
		candies.sort(reverse=True)
		i = 0
		j = N - 1
		maximum = 0
		while i <= j:
			maximum += candies[i]
			i += 1
			j -= K
		ans.append(maximum)
		return ans


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		mn = 0
		mx = 0
		buy = 0
		free = N - 1
		while buy <= free:
			mn += candies[buy]
			buy += 1
			free -= K
		buy = N - 1
		free = 0
		while buy >= free:
			mx += candies[buy]
			buy -= 1
			free += K
		return [mn, mx]


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		min = 0
		max = 0
		c = 0
		n = N
		while n > 0:
			n = n - 1 - K
			c = c + 1
		for i in range(c):
			min = min + candies[i]
			max = max + candies[N - 1 - i]
		return [min, max]


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		(a, b, j, n, i, m) = (0, 0, N - 1, N - 1, 0, 0)
		while i <= j and m <= n:
			a += candies[i]
			i += 1
			j -= K
			b += candies[n]
			m += K
			n -= 1
		return (a, b)


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		m = 0
		n = 0
		p = N
		for i in range(0, N, 1):
			if i < p:
				m = m + candies[i]
				n = n + candies[N - i - 1]
				p = p - K
		return (m, n)


class Solution:

	def candyStore(self, candies, N, K):
		res = []
		if K == 0:
			p = 0
			ts = 0
			for p in range(N):
				ts = ts + candies[p]
			res.append(ts)
			res.append(ts)
			return res
		else:
			candies.sort()
			sum = 0
			i = 0
			j = N - 1
			while i <= j:
				sum += candies[i]
				i += 1
				j -= K
			res.append(sum)
			sum1 = 0
			i1 = 0
			j1 = N - 1
			while i1 <= j1:
				sum1 += candies[j1]
				i1 += K
				j1 -= 1
			res.append(sum1)
			return res


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		a = []
		i = 0
		mins = 0
		j = N - 1
		while i <= j:
			mins += candies[i]
			i += 1
			j = j - K
		a.append(mins)
		candies.sort(reverse=True)
		i = 0
		maxx = 0
		j = N - 1
		while i <= j:
			maxx += candies[i]
			i += 1
			j = j - K
		a.append(maxx)
		return a


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		left = 0
		right = N - 1
		res = []
		minA = 0
		while left <= right:
			minA = minA + candies[left]
			left += 1
			right = right - K
		res.append(minA)
		maxA = 0
		left1 = 0
		right1 = N - 1
		while left1 <= right1:
			maxA += candies[right1]
			right1 -= 1
			left1 = left1 + K
		res.append(maxA)
		return res


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		s = 0
		if K == 0:
			for i in candies:
				s = s + i
			return (s, s)
		min = 0
		max = 0
		j = N - 1
		i = 0
		while i <= j:
			min = min + candies[i]
			j = j - K
			i = i + 1
		i = 0
		j = N - 1
		while i <= j:
			max = max + candies[j]
			j = j - 1
			i = i + K
		return (min, max)


class Solution:

	def candyStore(self, c, N, K):
		c.sort()
		l = 0
		r = N - 1
		l1 = []
		min = 0
		while l <= r:
			min += c[l]
			l += 1
			r = r - K
		l1.append(min)
		max = 0
		l = 0
		r = N - 1
		while l <= r:
			max += c[r]
			r -= 1
			l = l + K
		l1.append(max)
		return l1


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		(find_max, find_min) = (candies, candies)
		(maxa, mina) = (0, 0)
		buy = 0
		free = N - 1
		while buy <= free:
			mina += candies[buy]
			buy += 1
			free -= K
		buy = N - 1
		free = 0
		while free <= buy:
			maxa += candies[buy]
			buy -= 1
			free += K
		return (mina, maxa)


class Solution:

	def candyStore(self, candies, N, k):
		(m1, m3) = (0, 0)
		candies.sort()
		i = 0
		j = N - 1
		while i <= j:
			m1 += candies[i]
			i += 1
			j -= k
		i = 0
		j = N - 1
		while i <= j:
			m3 += candies[j]
			i += k
			j -= 1
		return [m1, m3]


class Solution:

	def candyStore(self, candies, N, K):
		asc = candies.copy()
		asc.sort()
		desc = candies.copy()
		desc.sort(reverse=True)
		min = 0
		max = 0
		i = 0
		j = N - 1
		while i <= j:
			min += asc[i]
			i += 1
			j -= K
		i = 0
		j = N - 1
		while i <= j:
			max += desc[i]
			i += 1
			j -= K
		return [min, max]


def shop_candy_store(candies: [], n, k):
	candies = sorted(candies)
	min_item = get_item_sorted_candy(candies, n, k)
	candies = list(reversed(candies))
	max_item = get_item_sorted_candy(candies, n, k)
	return [min_item, max_item]

def get_item_sorted_candy(candies: [], n: int, k):
	i = 0
	j = n - 1
	price_paid = 0
	while i <= j:
		price_paid = price_paid + candies[i]
		i = i + 1
		j = j - k
	return price_paid

class Solution:

	def candyStore(self, candies, N, K):
		return shop_candy_store(candies, N, K)


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		count = 0
		minCost = 0
		maxCost = 0
		for i in range(N):
			minCost += candies[i]
			count += K + 1
			if count >= N:
				break
		count = 0
		for i in range(N - 1, -1, -1):
			maxCost += candies[i]
			count += K + 1
			if count >= N:
				break
		return (minCost, maxCost)


from collections import deque

class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		a = deque([])
		for each in candies:
			a.append(each)
		b = a.copy()
		(res1, res2) = (0, 0)
		while len(a) > 0:
			cd = a.popleft()
			res1 += cd
			for i in range(K):
				if len(a) > 0:
					a.pop()
		b.reverse()
		while len(b) > 0:
			cd = b.popleft()
			res2 += cd
			for i in range(K):
				if len(b) > 0:
					b.pop()
		return (res1, res2)


class Solution:

	def candyStore(self, a, N, k):
		a.sort()
		min1 = 0
		max1 = 0
		total = N
		i = 0
		while total > 0:
			total -= 1 + k
			min1 += a[i]
			i += 1
		total = N
		j = N - 1
		while total > 0:
			total -= 1 + k
			max1 += a[j]
			j -= 1
		return [min1, max1]


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		i = 0
		j = N - 1
		min_cost = 0
		while i <= j:
			min_cost += candies[i]
			j -= K
			i += 1
		i = 0
		j = N - 1
		max_cost = 0
		while i <= j:
			max_cost += candies[j]
			i += K
			j -= 1
		return [min_cost, max_cost]


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		c = candies
		return (self.f1(c, N, K), self.f2(c, N, K))

	def f1(self, c, n, k):
		i = 0
		s = 0
		while i < n:
			s += c[i]
			n -= k
			i += 1
		return s

	def f2(self, c, n, k):
		i = n - 1
		(j, s) = (0, 0)
		while i >= j:
			s += c[i]
			i -= 1
			j += k
		return s


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		taken = 0
		toTake = 0
		while taken < N:
			toTake += 1
			taken += 1
			taken += K
		mini = 0
		maxi = 0
		for i in range(toTake):
			mini += candies[i]
			maxi += candies[N - 1 - i]
		return [mini, maxi]


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		a = N // (K + 1) + bool(N % (K + 1))
		return (sum(candies[:a]), sum(candies[N - a:]))


class Solution:

	def candyStore(self, candies, N, k):
		c = candies[:]
		candies.sort()
		(mc, i) = (0, 0)
		while candies and i < len(candies):
			mc += candies[i]
			for l in range(k):
				if candies:
					candies.pop()
			i += 1
		(mac, j) = (0, 0)
		c.sort(reverse=True)
		while c and j < len(c):
			mac += c[j]
			for m in range(k):
				if c:
					c.pop()
			j += 1
		return [mc, mac]


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		mi = minimum(candies, N, K)
		ma = maximum(candies, N, K)
		return (mi, ma)

def minimum(candies, N, K):
	i = 0
	res = 0
	while i < N:
		res += candies[i]
		i += 1
		N = N - K
	return res

def maximum(candies, N, K):
	i = N - 1
	res = 0
	index = 0
	while i >= index:
		res += candies[i]
		i -= 1
		index += K
	return res


class Solution:

	def candyStore(self, candies, N, K):
		if K == 0:
			return [sum(candies), sum(candies)]
		arr1 = sorted(candies)
		arr2 = sorted(candies, reverse=True)
		cnt1 = 0
		cnt2 = 0
		(l, r) = (0, N - 1)
		while l <= r:
			cnt1 += arr1[l]
			r -= K
			l += 1
		(l, r) = (0, N - 1)
		while l <= r:
			cnt2 += arr2[l]
			r -= K
			l += 1
		return [cnt1, cnt2]


class Solution:

	def candyStore(self, arr, n, k):
		arr.sort()
		mini = 0
		maxi = 0
		i = 0
		j = n - 1
		while i <= j:
			mini += arr[i]
			j -= k
			i += 1
		i = 0
		j = n - 1
		while i <= j:
			maxi += arr[j]
			j -= 1
			i += k
		return (mini, maxi)


class Solution:

	def candyStore(self, arr, n, k):
		arr.sort()
		buy = 0
		free = n - 1
		minc = 0
		while buy <= free:
			minc += arr[buy]
			buy += 1
			free -= k
		buy = n - 1
		free = 0
		maxc = 0
		while free <= buy:
			maxc += arr[buy]
			buy -= 1
			free += k
		return (minc, maxc)


class Solution:

	def candyStore(self, candies, N, k):
		if k == 0:
			s = sum(candies)
			return [s, s]
		candies = sorted(candies)
		i = 0
		j = N - 1
		ma = 0
		while i < j:
			ma = candies[i] + ma
			i += 1
			j = j - k
		if i == j:
			ma += candies[i]
		candies = candies[::-1]
		mi = 0
		i = 0
		j = N - 1
		while i < j:
			mi = candies[i] + mi
			i += 1
			j = j - k
		if i == j:
			mi += candies[i]
		return [ma, mi]


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		miniCost = 0
		buy = 0
		free = N - 1
		while buy <= free:
			miniCost += candies[buy]
			buy += 1
			free = free - K
		highCost = 0
		buy = N - 1
		free = 0
		while free <= buy:
			highCost += candies[buy]
			buy -= 1
			free = free + K
		return [miniCost, highCost]


class Solution:

	def candyStore(self, candies, n, k):
		candies.sort()
		maxStart = 0
		minEnd = n
		minCost = maxCost = 0
		for i in range(n):
			if i < minEnd:
				minCost += candies[i]
				minEnd -= k
			else:
				break
		for j in range(n - 1, -1, -1):
			if j >= maxStart:
				maxCost += candies[j]
				maxStart += k
			else:
				break
		return [minCost, maxCost]


class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		ans = []
		(maxsum, minsum) = (0, 0)
		(i, j) = (0, N - 1)
		while i <= j:
			minsum += candies[i]
			i += 1
			j -= K
		candies.sort(reverse=True)
		(i, j) = (0, N - 1)
		while i <= j:
			maxsum += candies[i]
			j -= K
			i += 1
		ans.append(minsum)
		ans.append(maxsum)
		return ans


import heapq

class Solution:

	def candyStore(self, candies, N, K):
		candies.sort()
		minc = 0
		maxc = 0
		if K == 0:
			return [sum(candies), sum(candies)]
		else:
			cnt = 0
			if N % (K + 1) > 0:
				cnt = 1
			for i in range(N // (K + 1) + cnt):
				minc += candies[i]
				maxc += candies[-i - 1]
		return [minc, maxc]


import math

class Solution:

	def candyStore(self, candies, N, K):
		c = math.ceil(N / (K + 1))
		candies.sort()
		return (sum(candies[:c]), sum(candies[-c:]))