There are 3n piles of coins of varying size, you and your friends will take piles of coins as follows:

In each step, you will choose any 3 piles of coins (not necessarily consecutive).
Of your choice, Alice will pick the pile with the maximum number of coins.
You will pick the next pile with maximum number of coins.
Your friend Bob will pick the last pile.
Repeat until there are no more piles of coins.

Given an array of integers piles where piles[i] is the number of coins in the ith pile.
Return the maximum number of coins which you can have.
 
Example 1:
Input: piles = [2,4,1,2,7,8]
Output: 9
Explanation: Choose the triplet (2, 7, 8), Alice Pick the pile with 8 coins, you the pile with 7 coins and Bob the last one.
Choose the triplet (1, 2, 4), Alice Pick the pile with 4 coins, you the pile with 2 coins and Bob the last one.
The maximum number of coins which you can have are: 7 + 2 = 9.
On the other hand if we choose this arrangement (1, 2, 8), (2, 4, 7) you only get 2 + 4 = 6 coins which is not optimal.

Example 2:
Input: piles = [2,4,5]
Output: 4

Example 3:
Input: piles = [9,8,7,6,5,1,2,3,4]
Output: 18

 
Constraints:

3 <= piles.length <= 10^5
piles.length % 3 == 0
1 <= piles[i] <= 10^4

Source: leetcode | Difficulty: MEDIUM
Tags: Sorting

Greedy algorithms

Game theory

Mathematics

Data structures

Starter code: class Solution:
    def maxCoins(self, piles: List[int]) -> int:
        

Solutions:
class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		i = 0
		j = len(piles) - 1
		max_coins = 0
		for i in range(len(piles) // 3, len(piles), 2):
			max_coins += piles[i]
		return max_coins


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort(reverse=True)
		return sum(piles[1:int(len(piles) / 3 * 2):2])


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles = sorted(piles)
		piles.reverse()
		ans = 0
		for i in range(len(piles) // 3):
			ans = ans + piles[2 * i + 1]
		return ans


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		list.sort(piles, reverse=True)
		print(piles)
		init = 0
		for j in range(len(piles) // 3):
			init = init + piles[j * 2 + 1]
		return init


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort(reverse=True)
		ans = 0
		i = 1
		j = len(piles) - 1
		while j - i >= 1:
			ans += piles[i]
			j -= 1
			i += 2
		return ans


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		rounds = []
		piles.sort()
		for i in range(int(len(piles) / 3)):
			round_draw = []
			round_draw.append(piles[i])
			round_draw.append(piles[-i * 2 - 2])
			round_draw.append(piles[-i * 2 - 1])
			rounds.append(round_draw)
		sum = 0
		for round_draw in rounds:
			sum += round_draw[1]
		return sum


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		result = 0
		piles.sort(reverse=True)
		for i in range(1, 2 * len(piles) // 3, 2):
			result += piles[i]
		return result


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		me = 0
		(start, end) = (0, len(piles) - 1)
		while start < end:
			if end - 1 > 0:
				me += piles[end - 1]
			(start, end) = (start + 1, end - 2)
		return me


class Solution:
	from collections import deque

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		n = len(piles) // 3
		s = piles[n:n * 3]
		return sum([s[i] for i in range(len(s)) if i % 2 == 0])


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		left = 0
		right = len(piles) - 2
		total = 0
		while left < right:
			total += piles[right]
			left += 1
			right -= 2
		return total


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		n = len(piles)
		piles = sorted(piles)
		piles = deque(piles)
		ans = 0
		while piles:
			piles.pop()
			ans += piles.pop()
			piles.popleft()
		return ans


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort(key=lambda k: k * -1)
		return sum(piles[1:len(piles) // 3 * 2:2])


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles = sorted(piles, key=lambda x: -x)
		result = 0
		for i in range(len(piles) // 3):
			result += piles[1 + 2 * i]
		return result


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		piles = deque(piles)
		me = 0
		while piles:
			alice = piles.pop()
			if piles:
				me += piles.pop()
			if piles:
				bob = piles.popleft()
		return me


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		rounds = len(piles) // 3
		score = 0
		piles.sort()
		for x in range(len(piles) - 2, rounds - 1, -2):
			score += piles[x]
		return score


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles = sorted(piles)
		coins = 0
		for i in range(len(piles) // 3, len(piles), 2):
			coins += piles[i]
		return coins


class Solution:

	def maxCoins(self, a: List[int]) -> int:
		a.sort()
		n = len(a)
		i = n // 3
		ans = 0
		while i < n:
			ans += a[i]
			i += 2
		return ans


import heapq

class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		choice = heapq.nlargest(len(piles) // 3 * 2, piles)
		ans = 0
		for i in range(1, len(choice), 2):
			ans += choice[i]
		return ans


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		piles = deque(piles)
		me = 0
		while len(piles) > 2:
			piles.pop()
			me += piles.pop()
			if piles:
				piles.popleft()
		return me


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		n = len(piles) // 3
		piles = piles[n:]
		return sum((piles[i * 2] for i in range(n)))


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort(reverse=True)
		i = 1
		x = len(piles)
		ans = []
		while i < x:
			ans.append(piles[i])
			x = x - 1
			i = i + 2
		return sum(ans)


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		num = int(len(piles) / 3)
		sor = sorted(piles)
		count = 0
		for i in range(1, num + 1):
			count += sor[num * 3 - i * 2]
		return count


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		n = len(piles)
		if n < 3:
			return 0
		current = n - 2
		low = 0
		total = 0
		while current > low:
			total += piles[current]
			current -= 2
			low += 1
		return total


from heapq import heappop, heappush, heapify

class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles = sorted(piles)
		(i, j) = (0, 0)
		ans = 0
		length = len(piles)
		while i + j < length - 1:
			i += 1
			j += 2
			ans += piles[-j]
		return ans


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		print(len(piles) % 3)
		piles = sorted(piles)
		print(piles)
		score = 0
		if len(piles) % 3 == 0:
			tmp = piles[int(len(piles) / 3):]
			nums = [tmp[i] for i in range(0, len(tmp), 2)]
			print(sum(nums))
			return sum(nums)
		elif len(piles) % 3 == 2:
			tmp = piles[int(len(piles) / 3):]
			nums = [tmp[i] for i in range(0, len(tmp), 2)]
			print(sum(nums))
			return sum(nums)
		else:
			tmp = piles[int(len(piles) / 3):]
			nums = [tmp[i] for i in range(1, len(tmp), 2)]
			print(sum(nums))
			return sum(nums)


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		return sum(piles[len(piles) // 3::2])


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		(i, j) = (0, len(piles) - 1)
		coins = 0
		while i < j:
			coins += piles[j - 1]
			i += 1
			j -= 2
		return coins


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		length = len(piles) // 3
		piles = piles[length:]
		me = 0
		alice = 0
		for i in range(len(piles)):
			if i % 2 == 0:
				me += piles[i]
			else:
				alice += piles[i]
		return me


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		arr = sorted(piles)
		res = []
		n = len(piles) // 3
		while len(arr) > n:
			arr.pop(-1)
			res.append(arr.pop(-1))
		return sum(res)


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		(first, last) = (0, len(piles) - 1)
		total = 0
		while first < last:
			total += piles[last - 1]
			first += 1
			last -= 2
		return total


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort(reverse=True)
		res = 0
		tims = len(piles) // 3
		for i in range(1, len(piles) - tims, 2):
			res += piles[i]
		return res
		pass


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		res = 0
		i = len(piles) - 2
		count = 1
		while count <= len(piles) / 3:
			res += piles[i]
			i -= 2
			count += 1
		return res


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles = sorted(piles)
		ans = 0
		i = 0
		j = len(piles) - 1
		while i < j:
			ans += piles[j - 1]
			j -= 2
			i += 1
		return ans


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		a = len(piles) // 3
		i = 0
		k = 1
		piles.sort(reverse=True)
		z = 0
		while i < a:
			z += piles[k]
			k = k + 2
			i = i + 1
		return z


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles = sorted(piles)
		n = len(piles)
		cost = 0
		left = 0
		right = n - 1
		for _ in range(n // 3):
			cost += piles[right - 1]
			left += 1
			right -= 2
		return cost


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles = sorted(piles)
		n = len(piles)
		s = 0
		for i in range(n // 3):
			s += piles[n - 1 - (2 * i + 1)]
		return s


class Solution:

	def maxCoins(self, a):
		a.sort()
		n = len(a)
		return sum((a[i] for i in range(n // 3, n, 2)))


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		st = deque(piles)
		mySum = 0
		while len(st) > 0:
			left = st.popleft()
			right = st.pop()
			urs = st.pop()
			mySum += urs
		return mySum


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		if len(piles) < 3:
			return 0
		res = 0
		piles.sort()
		for i in range(1, len(piles) // 3 + 1):
			res = res + piles[len(piles) - i * 2]
		return res


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort(reverse=1)
		res = 0
		rounds = len(piles) // 3
		for r in range(rounds):
			res += piles[r * 2 + 1]
		return res


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		result = 0
		piles.sort(reverse=True)
		index = 1
		counter = 0
		while counter < len(piles) // 3:
			result += piles[index]
			index += 2
			counter += 1
		return result


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		numOfTurns = int(len(piles) / 3)
		meAndAlice = piles[numOfTurns:]
		myTotal = 0
		for i in range(0, len(meAndAlice), 2):
			myTotal += meAndAlice[i]
		return myTotal


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		(min_, max_) = (min(piles), max(piles))
		cnt = [0 for i in range(min_, max_ + 1)]
		res = []
		v = 0
		for i in range(len(piles)):
			cnt[piles[i] - min_] += 1
		for i in range(len(cnt)):
			while cnt[i] > 0:
				res.append(i + min_)
				cnt[i] -= 1
		res = res[::-1]
		round_ = len(piles) // 3
		end = len(piles) - round_
		for i in res[1:end:2]:
			v += i
		return v


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		(me, alice, bob) = (0, 0, 0)
		i = 0
		j = len(piles) - 1
		while i < j - 1:
			bob += piles[i]
			i += 1
			me += piles[j - 1]
			alice += piles[j]
			j -= 2
		return me


from functools import cmp_to_key

def cmp(a, b):
	return b - a

class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort(key=cmp_to_key(cmp))
		tot = 0
		i = 1
		N = len(piles)
		n = int(N / 3)
		for i in range(1, N - n + 1, 2):
			tot += piles[i]
		return tot


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		mine = 0
		s = list(sorted(piles, reverse=True))
		for i in range(len(s) // 3):
			mine += s[2 * i + 1]
		return mine


from collections import deque

class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		coins = deque(sorted(piles, reverse=True))
		share = 0
		while coins:
			coins.pop()
			coins.popleft()
			share += coins.popleft()
		return share


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		sorted_piles = sorted(piles)
		piles_len = len(sorted_piles)
		start = int(piles_len / 3)
		counter = 0
		for x in range(start, piles_len, 2):
			counter += sorted_piles[x]
		return counter


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		result = 0
		i = len(piles) - 2
		while i >= int(len(piles) / 3):
			result += piles[i]
			i -= 2
		return result


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		our_coins = 0
		our_piles = 0
		l = len(piles) // 3
		piles.sort()
		pointer = -2
		while our_piles < l:
			our_piles += 1
			our_coins += piles[pointer]
			pointer -= 2
		return our_coins


from collections import deque

class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		l = len(piles)
		n = l // 3
		piles.sort()
		piles = deque(piles)
		ans = 0
		while piles:
			piles.pop()
			ans += piles.pop()
			piles.popleft()
		return ans


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		a = 0
		b = len(piles) - 2
		c = len(piles) - 1
		count = 0
		while a < len(piles) and b > 0 and (c > 0) and (a < b) and (a < c):
			count += piles[b]
			a += 1
			c -= 2
			b -= 2
		print(count)
		return count


import heapq

class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		res = 0
		heap = []
		for p in piles:
			heapq.heappush(heap, -p)
		for i in range(len(piles) // 3):
			heapq.heappop(heap)
			res += -heapq.heappop(heap)
		return res


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		res = 0
		x = 0
		test = []
		piles.sort()
		for i in range(len(piles) - 2, 0, -2):
			if x != len(piles) // 3:
				res += piles[i]
				test.append(piles[i])
				x += 1
		print(test)
		return res


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		size = len(piles)
		time = int(size / 3)
		(i, ans) = (0, 0)
		while i < time:
			ans += piles[size - 2 - i * 2]
			i += 1
		return ans


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		p = sorted(piles)
		n = len(piles)
		res = 0
		(l, r) = (0, n - 1)
		while l < r:
			res += p[r - 1]
			l += 1
			r -= 2
		return res


from typing import List
from collections import deque

class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		if len(piles) == 0:
			return 0
		piles.sort()
		piles_deque = deque(piles)
		my_take = 0
		while len(piles_deque) >= 3:
			alice_take = piles_deque.pop()
			my_take += piles_deque.pop()
			bob_take = piles_deque.popleft()
		return my_take


from collections import deque

class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles = deque(sorted(piles))
		my_coins = 0
		while piles:
			piles.pop()
			piles.popleft()
			my_coins += piles.pop()
		return my_coins


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		n = len(piles)
		alice_and_me = []
		max_piles = [-p for p in piles]
		heapq.heapify(max_piles)
		out = 0
		seen = 0
		while seen != n // 3:
			alice = heapq.heappop(max_piles)
			out -= heapq.heappop(max_piles)
			seen += 1
		return out


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		ret = 0
		LEN = len(piles)
		for i in range(LEN // 3):
			ret += piles[LEN - (i * 2 + 2)]
		return ret


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		l = len(piles) // 3
		piles.sort()
		piles = piles[l:]
		r = 0
		for (m, i) in enumerate(piles):
			if m % 2 == 0:
				r += i
		return r


import heapq

class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		maxheap = []
		for i in range(len(piles)):
			heapq.heappush(maxheap, piles[i] * -1)
		mine = 0
		size = len(maxheap)
		while size > 0:
			heapq.heappop(maxheap)
			middle = heapq.heappop(maxheap)
			middle *= -1
			mine += middle
			size -= 3
		return mine


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		numRounds = len(piles) // 3
		ret = 0
		for i in range(len(piles) - 1, numRounds - 1, -2):
			ret += min(piles[i], piles[i - 1])
		return ret


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles = sorted(piles)
		sum = 0
		for n in range(len(piles) // 3, len(piles), 2):
			sum = sum + piles[n]
		return sum


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		[8, 7, 4, 2, 2, 1]
		n = len(piles)
		if n <= 1:
			return 0
		sorted_piles = sorted(piles, reverse=True)
		print(sorted_piles)
		(s, e) = (1, n - 1)
		ans = 0
		while s < e:
			ans += sorted_piles[s]
			s += 2
			e -= 1
		return ans


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		d = [0] * 10 ** 4
		t = 0
		total = 0
		for p in piles:
			d[p - 1] += 1
		for i in range(len(d)):
			while d[i] > 0:
				d[i] -= 1
				if t >= len(piles) // 3 and t % 2 == len(piles) // 3 % 2:
					total += i + 1
				t += 1
		return total


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		que = deque(sorted(piles)[::-1])
		res = 0
		while len(que) > 2:
			que.popleft()
			res += que.popleft()
			que.pop()
		return res


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		n = len(piles) // 3
		piles.sort(reverse=True)
		count = 0
		j = 1
		for i in range(n):
			count += piles[j]
			j += 2
		return count


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort(reverse=True)
		(coins, turns, idx) = (0, 0, 1)
		while turns < len(piles) // 3:
			coins += piles[idx]
			idx += 2
			turns += 1
		return coins


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		if len(piles) == 3:
			return piles[1]
		print(len(piles) % 2)
		print(list(((i, a) for (i, a) in enumerate(sorted(piles)[len(piles) // 3:]) if i % 2 == len(piles) % 2)))
		return sum((a for (i, a) in enumerate(sorted(piles)[len(piles) // 3:]) if i % 2 == 0))


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		piles.reverse()
		l = len(piles) // 3
		p = len(piles) - l
		s = sum([piles[i] for i in range(1, p, 2)])
		return s


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		maxCoins = 0
		count = len(piles)
		while count > 0:
			piles.pop(0)
			maxCoins += piles.pop(-2)
			piles.pop(-1)
			count = len(piles)
		return maxCoins


class Solution:

	def maxCoins(self, piles):
		choose = 0
		piles = sorted(piles, reverse=True)
		for i in range(len(piles) // 3):
			choose += piles[2 * i + 1]
		return choose


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		q = collections.deque(piles)
		count = 0
		while len(q) > 0:
			q.popleft()
			q.pop()
			count += q[-1]
			q.pop()
		return count


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		max_index = len(piles) - 2
		result = 0
		piles.sort()
		for _ in range(len(piles) // 3):
			result += piles[max_index]
			max_index -= 2
		return result


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort(reverse=True)
		s = 0
		for i in range(0, len(piles), 2):
			x = piles.pop()
			try:
				s += piles[i + 1]
			except:
				print('')
		return s


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort(reverse=True)
		n = len(piles) // 3
		i = 1
		res = 0
		while i < 2 * n:
			res += piles[i]
			i += 2
		return res


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		triples = []
		count = len(piles)
		while count > 0:
			newTrip = []
			newTrip = [piles[0], piles[-2], piles[-1]]
			triples.append(newTrip)
			piles.pop(0)
			piles.pop(-2)
			piles.pop(-1)
			count = len(piles)
		maxCoins = 0
		for i in range(len(triples)):
			maxCoins += triples[i][1]
		return maxCoins


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		rounds = int(len(piles) / 3)
		max_el = 0
		while rounds != 0:
			piles.pop()
			max_el += piles[-1]
			piles.pop()
			piles.pop(0)
			rounds -= 1
		return max_el


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		wallet = 0
		while piles:
			piles.pop()
			wallet += piles.pop()
			del piles[0]
		return wallet


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		ret_num = 0
		while piles:
			piles.pop(0)
			piles.pop()
			ret_num += piles.pop()
		return ret_num


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		my_coins = 0
		piles = sorted(piles)
		while piles:
			del piles[0]
			del piles[-1]
			my_coins += piles[-1]
			del piles[-1]
		return my_coins


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		if not piles:
			return 0
		rounds = len(piles) // 3
		max_heap = []
		min_heap = []
		for n in piles:
			heapq.heappush(max_heap, -n)
			heapq.heappush(min_heap, n)
		res = 0
		while rounds > 0:
			rounds -= 1
			(alex, me) = (-heapq.heappop(max_heap), -heapq.heappop(max_heap))
			res += me
		return res


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		numCoins = 0
		piles.sort()
		while len(piles) > 0:
			piles.pop()
			numCoins += piles.pop()
			piles.pop(0)
		return numCoins


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		a = 0
		y = 0
		b = 0
		while piles != []:
			a = a + piles.pop()
			y = y + piles.pop()
			b = b + piles.pop(0)
		return y


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		sums = 0
		while piles:
			(m1, m2) = (piles.pop(), piles.pop())
			m3 = piles.pop(0)
			sums += m2
		return sums


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		result = 0
		while len(piles) > 0:
			piles.pop()
			result += piles.pop()
			piles.pop(len(piles) // 3)
		return result


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		n = len(piles)
		t = 0
		piles.sort()
		for i in range(n // 3 - 1):
			t += piles[-2]
			piles.pop(0)
			piles.pop(-1)
			piles.pop(-2)
		t += piles[-2]
		return t


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles = sorted(piles, reverse=True)
		num2 = len(piles) // 3
		piles = piles[:-num2]
		print(piles)
		return sum((el for (i, el) in enumerate(piles) if i % 2 == 1))


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		max_coins_for_me = 0
		sorted_piles = sorted(piles)
		while len(sorted_piles) > 0:
			alice = sorted_piles.pop()
			max_coins_for_me += sorted_piles.pop()
			bob = sorted_piles.pop(0)
		return max_coins_for_me


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		sorted_piles = sorted(piles)
		res = 0
		while sorted_piles:
			sorted_piles.pop()
			res += sorted_piles.pop()
			sorted_piles.pop(0)
		return res


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		sorted_piles = list(sorted(piles))
		s = 0
		while len(sorted_piles) > 3:
			s += sorted_piles[-2]
			sorted_piles.pop(0)
			sorted_piles.pop(-2)
			sorted_piles.pop(-1)
		s += sorted_piles[-2]
		return s


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		sorted_piles = sorted(piles)
		your_total = 0
		while sorted_piles:
			sorted_piles.pop(0)
			sorted_piles.pop(-1)
			your_total += sorted_piles.pop(-1)
		return your_total


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		coins = 0
		sorted_piles = sorted(piles)
		while len(sorted_piles):
			sorted_piles.pop()
			coins += sorted_piles.pop()
			sorted_piles.pop(0)
		return coins


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		num_coins = 0
		sorted_piles = list(sorted(piles))
		while len(sorted_piles):
			my_choice = sorted_piles[-2]
			num_coins += my_choice
			del sorted_piles[-2]
			del sorted_piles[0]
			del sorted_piles[-1]
		return num_coins


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		n = len(piles) / 3
		res = 0
		p = sorted(piles)
		for i in range(int(n)):
			p.pop(-1)
			p.pop(0)
			res += p[-1]
			p.pop(-1)
		return res


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		length = len(piles)
		maxSum = 0
		for i in range(int(length / 3)):
			maxSum += piles[-2]
			piles.pop(-1)
			piles.pop(-1)
			piles.pop(0)
		return maxSum


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		s = len(piles) // 3
		n = len(piles)
		(i, j, k) = (0, n - 2, n - 1)
		sumi = 0
		while s != 0:
			sumi += piles[j]
			j = j - 2
			s = s - 1
		return sumi


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		mine = 0
		while piles:
			piles.pop(-1)
			mine += piles.pop(-1)
			piles.pop(0)
		return mine


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		res = 0
		while len(piles) != 0:
			can = []
			can.append(piles.pop())
			can.append(piles.pop())
			can.append(piles.pop(0))
			res += can[1]
			can = []
		return res


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		newP = []
		pileSort = sorted(piles)
		while len(pileSort) > 0:
			newP.append([pileSort[0], pileSort[-2], pileSort[-1]])
			pileSort.pop(0)
			pileSort.pop(-2)
			pileSort.pop(-1)
		sum = 0
		for i in newP:
			sum += i[1]
		return sum


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		res = 0
		while piles:
			first = piles.pop(-1)
			second = piles.pop(-1)
			third = piles.pop(0)
			res += second
		return res


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		mine = []
		while piles:
			_ = piles.pop()
			_ = piles.pop(0)
			mine.append(piles.pop())
		return sum(mine)


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		me = 0
		piles = sorted(piles)
		while len(piles) > 1:
			temp = [piles[0]] + piles[-2:]
			piles.pop(0)
			piles.pop(-1)
			piles.pop(-1)
			temp = sorted(temp)
			me += temp[1]
		return me


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles = sorted(piles, key=lambda x: -x)
		(ans, cnt) = (0, 0)
		for i in range(1, len(piles), 2):
			ans += piles[i]
			cnt += 1
			if cnt == len(piles) // 3:
				break
		return ans


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		sorted_piles = piles
		sorted_piles.sort()
		max_coins = 0
		num_groups = int(len(sorted_piles) / 3)
		for i in range(num_groups):
			sorted_piles.pop(len(sorted_piles) - 1)
			sorted_piles.pop(0)
			your_coin = sorted_piles.pop(len(sorted_piles) - 1)
			max_coins += your_coin
		return max_coins


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		count_total = 0
		while len(piles) > 0:
			max_el = piles.pop(-1)
			second_max_el = piles.pop(-1)
			min_el = piles.pop(0)
			count_total += second_max_el
		return count_total


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		sorted_coins = sorted(piles)
		print(sorted_coins)
		max_coins = 0
		while len(sorted_coins) > 0:
			sorted_coins.pop(0)
			sorted_coins.pop()
			max_coins += sorted_coins.pop()
		return max_coins


class Solution:

	def maxCoins(self, piles: List[int]) -> int:

		def mergeSort(l):
			if len(l) < 2:
				return l
			pivot = l[0]
			return mergeSort([x for x in l if x > pivot]) + [x for x in l if x == pivot] + mergeSort([x for x in l if x < pivot])
		sortedPiles = mergeSort(piles)
		sumlimit = 2 * len(piles) // 3
		sumind = list(range(1, sumlimit, 2))
		return sum([sortedPiles[i] for i in sumind])


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		ans = 0
		while len(piles) != 0:
			piles.pop(0)
			piles.pop(-1)
			ans += piles.pop(-1)
		return ans


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort(reverse=True)
		print(piles)
		p3n = len(piles)
		n = int(p3n / 3)
		out = 0
		i = 1
		while i < 2 * n:
			out += piles[i]
			print(piles[i])
			i += 2
		return out


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles = sorted(piles)
		return self.helper(piles)

	def helper(self, piles):
		if not piles:
			return 0
		mx = piles[-1]
		mx2 = piles[-2]
		mn = piles[0]
		piles.pop(0)
		piles.pop()
		piles.pop()
		return mx2 + self.helper(piles)


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		Count = 0
		while piles:
			Count += piles[-2]
			piles.pop()
			piles.pop()
			piles.pop(0)
		return Count


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		ans = 0
		while piles:
			big = piles.pop()
			ans += piles.pop()
			smol = piles.pop(0)
		return ans


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		ans = 0
		while len(piles) >= 3:
			bade_bahi = piles.pop()
			mei_khud = piles.pop()
			chutiya = piles.pop(0)
			ans += mei_khud
		return ans


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		me = 0
		piles.sort()
		while piles:
			arr = []
			arr += (piles.pop(),)
			arr += (piles.pop(),)
			arr += (piles.pop(0),)
			arr.sort()
			me += arr.pop(1)
		return me


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		answer = 0
		while len(piles) > 0:
			largest = piles.pop()
			almostLargest = piles.pop()
			smallest = piles.pop(0)
			answer += almostLargest
		return answer


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		complete_sorted = sorted(piles)
		result = 0
		while complete_sorted:
			complete_sorted.pop()
			result += complete_sorted.pop()
			complete_sorted.pop(0)
		return result


from collections import deque

class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		ret = 0
		d = deque(sorted(piles))

		def draw(ds):
			nonlocal ret
			discard = ds.pop()
			ret += ds.pop()
			discard = ds.popleft()
			return ds
		while len(d) >= 3:
			d = draw(d)
		return ret


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		res = 0
		while piles:
			a = piles.pop()
			b = piles.pop()
			c = piles.pop(0)
			res += b
		return res


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		a = 0
		(first, moke, myself) = (0, 0, 0)
		i = 0
		j = len(piles) - 1
		while i < j:
			first += piles[j]
			j -= 1
			myself += piles[j]
			j -= 1
			moke += piles[i]
			i += 1
		return myself


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		wallet = 0
		start = 0
		end = len(piles) - 1
		while start <= end:
			start += 1
			end -= 1
			wallet += piles[end]
			end -= 1
		return wallet


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		piles = deque(piles)
		res = 0
		while piles:
			piles.pop()
			res += piles.pop()
			piles.popleft()
		return res


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		ans = 0
		queue = collections.deque()
		piles.sort()
		for ele in piles:
			queue.append(ele)
		while len(queue):
			queue.popleft()
			queue.pop()
			ans += queue.pop()
		return ans


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		my_coins = 0
		piles.sort()
		count = len(piles) / 3
		i = 0
		j = -2
		k = -1
		while count > 0:
			my_coins += piles[j]
			i += 1
			j -= 2
			k -= 2
			count -= 1
		return my_coins


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		asc = sorted(piles)
		desc = sorted(piles, reverse=True)
		new = []
		for i in range(len(piles) // 3):
			new.append(asc.pop())
			new.append(asc.pop())
			new.append(desc.pop())
		return sum([new[i] for i in range(len(new)) if i % 3 == 1])


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		return sum(sorted(piles)[-2:-2 * (len(sorted(piles)) // 3) - 1:-2])


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		s_piles = sorted(piles)
		my_coin_ct = 0
		triplet_ct = len(s_piles) // 3
		for i in range(triplet_ct, 0, -1):
			my_coin_ct += s_piles[2 * (i - 1) + triplet_ct]
		return my_coin_ct


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		me_max = 0
		start = len(piles) - 2
		for i in range(int(len(piles) / 3)):
			idx = start - 2 * i
			me_max += piles[idx]
		return me_max


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		out = 0
		count = 0
		hi = len(piles) - 1
		lo = 0
		while count < len(piles):
			if count % 3 == 0:
				hi -= 1
			elif count % 3 == 1:
				out += piles[hi]
				hi -= 1
			else:
				lo += 1
			count += 1
		return out


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles = collections.deque(sorted(piles)[::-1])
		s = 0
		while len(piles) > 0:
			piles.popleft()
			x = piles.popleft()
			piles.pop()
			s += x
		return s


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		l = len(piles)
		temp = 2
		sum = 0
		for i in range(l // 3):
			sum = sum + piles[l - temp]
			temp = temp + 2
		return sum


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		heap = [-x for x in piles]
		heapq.heapify(heap)
		rounds = count = 0
		while len(heap) > rounds:
			_ = heapq.heappop(heap)
			count -= heapq.heappop(heap)
			rounds += 1
		return count


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		if not piles:
			return 0
		piles.sort()
		coins = 0
		n = len(piles)
		index = n - 2
		for i in range(n // 3):
			coins += piles[index]
			index -= 2
		return coins


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles = sorted(piles)
		(me, alice, bob) = (len(piles) - 2, 0, len(piles))
		ans = 0
		while alice < me:
			ans += piles[me]
			alice += 1
			me -= 2
			bob -= 2
		return ans


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		count1 = int(len(piles) / 3)
		sum1 = 0
		j = 0
		while count1 < len(piles):
			print(j, count1)
			if j % 2 == 0:
				print(piles[count1])
				sum1 = sum1 + piles[count1]
			count1 = count1 + 1
			j = j + 1
		return sum1


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		count = 0
		coinPiles = collections.deque(sorted(piles))
		while len(coinPiles) > 0:
			coinPiles.pop()
			count += coinPiles.pop()
			coinPiles.popleft()
		return count


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		length = len(piles)
		sorted_piles = sorted(piles, reverse=True)
		if length == 3:
			return sorted_piles[1]
		n = length / 3
		(count, res) = (0, 0)
		for i in range(1, length, 2):
			if count == n:
				return res
			res += sorted_piles[i]
			count += 1


import heapq

class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		max_coins_for_me = 0
		sorted_piles = sorted(piles)
		top = len(piles) - 1
		for i in range(len(piles) // 3):
			max_coins_for_me += sorted_piles[top - 1]
			top = top - 2
		return max_coins_for_me


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort(reverse=True)
		res = 0
		(alice, me, bob) = (0, 1, -1)
		while me < len(piles) + bob:
			res += piles[me]
			alice += 2
			me += 2
			bob -= 1
		return res


import heapq

class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles = sorted(piles)
		piles = piles[len(piles) // 3:]
		me = 0
		for i in range(len(piles) - 2, -1, -2):
			me += piles[i]
		return me


class Solution:

	def maxCoins(self, p: List[int]) -> int:
		p.sort()
		max_coins = 0
		i = len(p) // 3
		while i < len(p):
			max_coins += p[i]
			i += 2
		return max_coins


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		n = len(piles) // 3
		mc = 0
		piles.sort(reverse=True)
		print(piles)
		for i in range(0, n):
			mc += piles[1 + 2 * i]
		return mc


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		you = []
		l = int(len(piles) / 3)
		piles.sort()
		piles = piles[l:]
		for i in range(len(piles)):
			if i % 2 == 0:
				you.append(piles[i])
		return sum(you)


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		total = 0
		n = len(piles) // 3
		m = len(piles) - 1
		for i in range(m, n, -2):
			total += piles[i - 1]
		return total


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		c = 0
		for x in range(len(piles) // 3, len(piles), 2):
			c += piles[x]
		return c


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		(l_i, r_i) = (0, len(piles) - 1)
		max_coin = 0
		while l_i < r_i:
			max_coin += piles[r_i - 1]
			l_i += 1
			r_i -= 2
		return max_coin


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		count = 0
		piles.sort()
		l = len(piles)
		n = l // 3
		j = l - 2
		k = 0
		while k < n:
			count = count + piles[j]
			j = j - 2
			k = k + 1
		return count


from collections import deque

class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		piles = deque(piles)
		total = 0
		(ptr1, ptr2) = (len(piles) - 2, 0)
		while ptr2 < ptr1:
			total += piles[ptr1]
			ptr1 -= 2
			ptr2 += 1
		return total


class Solution:

	def maxCoins(self, piles):
		piles.sort()
		end = len(piles) - 2
		start = 0
		count = 0
		while start < end:
			count += piles[end]
			end -= 2
			start += 1
		return count


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		piles.sort()
		piles = piles[::-1]
		return sum((piles[x] for x in range(1, 2 * len(piles) // 3, 2)))


class Solution:

	def maxCoins(self, piles: List[int]) -> int:
		if len(piles) == 3:
			return piles[1]
		return sum((a for a in sorted(piles)[len(piles) // 3::2]))


class Solution:

	def maxCoins(self, piles: List[int]) -> int:

		def dps():

			def remove_from_first(T, s):
				assert len(s) == 3
				L = list(T)
				for x in s:
					if x in L:
						L.remove(x)
				return tuple(L)
			from itertools import combinations
			from functools import lru_cache

			@lru_cache(None)
			def dp(T):
				if len(T) == 0:
					return 0
				if len(T) == 3:
					return sum(T) - max(T) - min(T)
				mxl = 0
				for cm in combinations(T, 3):
					S = remove_from_first(T, cm)
					mxl = max(mxl, dp(S) + sum(cm) - max(cm) - min(cm))
				return mxl
			return dp(tuple(piles))

		def iter_appr():
			assert len(piles) % 3 == 0
			(maxheap, minheap) = ([], [])
			counter = 0
			from heapq import heappush, heappop
			for x in piles:
				heappush(maxheap, -x)
				heappush(minheap, x)
			(alice, me, bob) = (0, 0, 0)
			while maxheap and minheap and (counter < len(piles)):
				alice += -heappop(maxheap)
				me += -heappop(maxheap)
				bob += heappop(minheap)
				counter += 3
			return me
		return iter_appr()