На тренировку по подготовке к соревнованиям по программированию пришли n команд. Тренер для каждой команды подобрал тренировку, комплект задач для i-й команды занимает a_{i} страниц. В распоряжении тренера есть x листов бумаги, у которых обе стороны чистые, и y листов, у которых только одна сторона чистая. При печати условия на листе первого типа можно напечатать две страницы из условий задач, а при печати на листе второго типа — только одну. Конечно, на листе нельзя печатать условия из двух разных комплектов задач. Обратите внимание, что при использовании листов, у которых обе стороны чистые, не обязательно печатать условие на обеих сторонах, одна из них может остаться чистой.

Вам предстоит определить максимальное количество команд, которым тренер сможет напечатать комплекты задач целиком.


-----Входные данные-----

В первой строке входных данных следуют три целых числа n, x и y (1 ≤ n ≤ 200 000, 0 ≤ x, y ≤ 10^9) — количество команд, количество листов бумаги с двумя чистыми сторонами и количество листов бумаги с одной чистой стороной.

Во второй строке входных данных следует последовательность из n целых чисел a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10 000), где i-е число равно количеству страниц в комплекте задач для i-й команды.


-----Выходные данные-----

Выведите единственное целое число — максимальное количество команд, которым тренер сможет напечатать комплекты задач целиком.


-----Примеры-----
Входные данные
2 3 5
4 6

Выходные данные
2

Входные данные
2 3 5
4 7

Выходные данные
2

Входные данные
6 3 5
12 11 12 11 12 11

Выходные данные
1



-----Примечание-----

В первом тестовом примере можно напечатать оба комплекта задач. Один из возможных ответов — напечатать весь первый комплект задач на листах с одной чистой стороной (после этого останется 3 листа с двумя чистыми сторонами и 1 лист с одной чистой стороной), а второй комплект напечатать на трех листах с двумя чистыми сторонами.

Во втором тестовом примере можно напечатать оба комплекта задач. Один из возможных ответов — напечатать первый комплект задач на двух листах с двумя чистыми сторонами (после этого останется 1 лист с двумя чистыми сторонами и 5 листов с одной чистой стороной), а второй комплект напечатать на одном листе с двумя чистыми сторонами и на пяти листах с одной чистой стороной. Таким образом, тренер использует все листы для печати.

В третьем тестовом примере можно напечатать только один комплект задач (любой из трёх 11-страничных). Для печати 11-страничного комплекта задач будет израсходована вся бумага.

Difficulty: MEDIUM

Starter code:

Solutions:
import sys, math
(n, x, y) = list(map(int, input().split()))
z = list(map(int, input().split()))
z.sort()
ans = 0
for i in range(n):
	if z[i] % 2 == 0:
		if x >= z[i] // 2:
			x -= z[i] // 2
			ans += 1
		else:
			z[i] -= x * 2
			x = 0
			y -= z[i]
			if y >= 0:
				ans += 1
			else:
				break
	elif x >= z[i] // 2 and y >= 1:
		x -= z[i] // 2
		ans += 1
		y -= 1
	elif x >= z[i] // 2 + 1:
		x -= z[i] // 2 + 1
		ans += 1
	else:
		z[i] -= x * 2
		x = 0
		y -= z[i]
		if y >= 0:
			ans += 1
		else:
			break
print(ans)


(n, x, y) = list(map(int, input().split()))
teams = list(map(int, input().split()))
teams.sort()
c = 0
for team in teams:
	if x:
		pages_to_print = min(team // 2, x)
		x -= pages_to_print
		team -= pages_to_print * 2
	if team:
		if y:
			pages_to_print = min(team, y)
			y -= pages_to_print
			team -= pages_to_print
		if team:
			pages_to_print = sum(divmod(team, 2))
			if pages_to_print > x:
				break
			x -= pages_to_print
	c += 1
print(c)


[n, x, y] = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
c = 0
for i in a:
	chislo = i
	if chislo // 2 <= x:
		ax = i // 2
	else:
		ax = x
	x -= ax
	chislo = chislo - ax * 2
	ay = min(chislo, y)
	y -= ay
	chislo = chislo - ay
	if chislo != 0 and x != 0:
		x -= 1
		chislo -= 1
	if chislo == 0:
		c += 1
	else:
		break
print(c)


(n, x, y) = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
x *= 2
for i in range(n):
	kol = x + y
	if kol >= a[i]:
		if a[i] % 2 != 0:
			if y > 0:
				y -= 1
				a[i] -= 1
			else:
				x -= 2
				a[i] -= 1
		x -= a[i]
		if x < 0:
			y += x
			x = 0
	else:
		print(i)
		break
else:
	print(i + 1)


xy = [0, 0]

def check(k):
	nonlocal xy
	(x, y) = xy
	got = True
	if y * 2 > k:
		y -= k // 2
		if k % 2 != 0:
			if x != 0:
				x -= 1
			elif y != 0:
				y -= 1
			else:
				got = False
	else:
		k -= y * 2
		y = 0
		if k <= x:
			x -= k
		else:
			got = False
	xy = [x, y]
	return got
(n, y, x) = map(int, input().split())
k = sorted(map(int, input().split()))
cnt = 0
xy = [x, y]
while cnt < n and check(k[cnt]):
	cnt += 1
print(cnt)


(n, x, y) = list(map(int, input().split()))
arr = list(map(int, input().split()))
arr.sort()
s = 0
for i in range(n):
	if x * 2 >= arr[i]:
		x -= arr[i] // 2
		arr[i] %= 2
	else:
		arr[i] -= x * 2
		x = 0
	if y >= arr[i]:
		y -= arr[i]
		arr[i] = 0
	if x >= arr[i]:
		x -= arr[i]
		arr[i] = 0
	if arr[i] > 0:
		break
	s += 1
print(s)


M = input().split()
n = int(M[0])
x = int(M[1])
y = int(M[2])
M = input().split()
for i in range(0, n):
	M[i] = int(M[i])
M.sort()
c = 0
for i in range(0, n):
	if M[i] > 0:
		dy = M[i] % 2
		dx = (M[i] - dy) // 2
		x = x - dx
		y = y - dy
		if x < 0:
			y += x * 2
			x = 0
			if y < 0:
				break
		if y < 0:
			x += y
			y = 0
			if x < 0:
				break
		if x >= 0 and y >= 0:
			c += 1
	M[i] = 0
	if x == 0 and y == 0:
		break
ndone = n
for i in range(0, n):
	if M[i] > 0:
		ndone += -1
print(ndone)


def main():
	read = lambda : list(map(int, input().split()))
	(n, x, y) = read()
	a = sorted(read())
	cnt = 0
	for k in a:
		if 2 * x + y < k:
			break
		if k % 2 == 0 and 2 * x >= k:
			cx = k // 2
			cy = 0
		elif k % 2 == 0 and 2 * x < k:
			cx = x
			cy = k - 2 * cx
		elif k % 2 and y:
			cx = k // 2
			cy = 1
		elif k % 2 and y == 0:
			cx = k // 2 + 1
			cy = 0
		y -= cy
		x -= cx
		cnt += 1
	print(cnt)
main()