A group of tourists is going to kayak and catamaran tour. A rented lorry has arrived to the boat depot to take kayaks and catamarans to the point of departure. It's known that all kayaks are of the same size (and each of them occupies the space of 1 cubic metre), and all catamarans are of the same size, but two times bigger than kayaks (and occupy the space of 2 cubic metres).

Each waterborne vehicle has a particular carrying capacity, and it should be noted that waterborne vehicles that look the same can have different carrying capacities. Knowing the truck body volume and the list of waterborne vehicles in the boat depot (for each one its type and carrying capacity are known), find out such set of vehicles that can be taken in the lorry, and that has the maximum total carrying capacity. The truck body volume of the lorry can be used effectively, that is to say you can always put into the lorry a waterborne vehicle that occupies the space not exceeding the free space left in the truck body.

Input

The first line contains a pair of integer numbers n and v (1 ≤ n ≤ 105; 1 ≤ v ≤ 109), where n is the number of waterborne vehicles in the boat depot, and v is the truck body volume of the lorry in cubic metres. The following n lines contain the information about the waterborne vehicles, that is a pair of numbers ti, pi (1 ≤ ti ≤ 2; 1 ≤ pi ≤ 104), where ti is the vehicle type (1 – a kayak, 2 – a catamaran), and pi is its carrying capacity. The waterborne vehicles are enumerated in order of their appearance in the input file.

Output

In the first line print the maximum possible carrying capacity of the set. In the second line print a string consisting of the numbers of the vehicles that make the optimal set. If the answer is not unique, print any of them.

Examples

Input

3 2
1 2
2 7
1 3


Output

7
2

Difficulty: HARD
Tags: Sorting

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
(n, v) = map(int, input().split())
a = []
b = []
for i in range(n):
	(typ, carry) = map(int, input().split())
	if typ == 1:
		a.append([carry, i + 1])
	else:
		b.append([carry, i + 1])
a.sort(reverse=True)
b.sort(reverse=True)
for i in range(1, len(a)):
	a[i][0] += a[i - 1][0]
for i in range(1, min(len(b), v // 2)):
	b[i][0] += b[i - 1][0]
res = [0, 0, 0]
r = range(0, min(v, len(a)) + 1)
for i in r:
	j = int(min((v - i) // 2, len(b)))
	v1 = 0
	if i:
		v1 = a[i - 1][0]
	v2 = 0
	if j:
		v2 = b[j - 1][0]
	if res[0] < v1 + v2:
		res = [v1 + v2, i, j]
print(res[0])
path = []
if res[1]:
	for i in range(res[1]):
		path.append(a[i][1])
if res[2]:
	for i in range(res[2]):
		path.append(b[i][1])
print(' '.join((str(i) for i in path)))


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
import time
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def isInt(s):
	return '0' <= s[0] <= '9'
MOD = 10 ** 9 + 7

def solve():
	(N, V) = getInts()
	(kayaks, cats) = ([], [])
	for n in range(N):
		(t, p) = getInts()
		if t == 1:
			kayaks.append((p, n + 1))
		else:
			cats.append((p, n + 1))
	kayaks.sort(reverse=True)
	cats.sort(reverse=True)
	k_pref = [0]
	curr = 0
	for (k, k2) in kayaks:
		curr += k
		k_pref.append(curr)
	c_pref = [0]
	curr = 0
	for (c, c2) in cats:
		curr += c
		c_pref.append(curr)
	ans = 0
	ans_k = ans_c = 0
	for k in range(0, len(kayaks) + 1):
		if k > V:
			break
		tmp = k_pref[k]
		rem_vol = V - k
		num_cats = min(rem_vol // 2, len(cats))
		tmp += c_pref[num_cats]
		if tmp > ans:
			ans = tmp
			ans_k = k
			ans_c = num_cats
	print(ans)
	ans_str = []
	for i in range(ans_k):
		ans_str.append(kayaks[i][1])
	for i in range(ans_c):
		ans_str.append(cats[i][1])
	print(*ans_str)
	return
solve()


from sys import stdin
(n, v) = [int(x) for x in stdin.readline().split()]
k = []
c = []
for x in range(n):
	(a, b) = [int(x) for x in stdin.readline().split()]
	if a == 1:
		k.append((b, x + 1))
	else:
		c.append((b, x + 1))
k.sort()
c.sort()
cap = 0
boats = []
if v % 2 == 1 and k:
	x = k.pop()
	cap += x[0]
	boats.append(x[1])
for x in range(v // 2):
	if not k and (not c):
		break
	kN = 0
	cN = 0
	if len(k) >= 2:
		kN = k[-1][0] + k[-2][0]
	elif k:
		kN = k[-1][0]
	if c:
		cN = c[-1][0]
	if kN > cN:
		cap += kN
		boats.append(k.pop()[1])
		if k:
			boats.append(k.pop()[1])
	else:
		cap += cN
		boats.append(c.pop()[1])
print(cap)
print(' '.join([str(x) for x in boats]))


(n, v) = map(int, input().split(' '))
(a, b) = ([], [])
for i in range(n):
	(t, p) = map(int, input().split(' '))
	if t == 1:
		a.append([p, i + 1])
	else:
		b.append([p, i + 1])
a.sort(reverse=True)
b.sort(reverse=True)
(i, j) = (0, 0)
while v > 0 and i + j < n:
	if v == 1:
		if i < len(a):
			v -= 1
			i += 1
		if v == 0 and i > 1 and (j < len(b)) and (a[i - 1][0] + a[i - 2][0] < b[j][0]):
			i -= 2
			j += 1
		if v == 1 and i > 0 and (j < len(b)) and (a[i - 1][0] < b[j][0]):
			v -= 1
			i -= 1
			j += 1
		break
	elif i < len(a) and j < len(b):
		if a[i][0] * 2 > b[j][0]:
			v -= 1
			i += 1
		else:
			v -= 2
			j += 1
	elif i < len(a):
		v -= 1
		i += 1
	else:
		v -= 2
		j += 1
(a, b) = (a[:i], b[:j])
capacity = sum([t[0] for t in a]) + sum([t[0] for t in b])
s = [t[1] for t in a] + [t[1] for t in b]
print(capacity)
print(' '.join(map(str, s)))


(n, v) = map(int, input().split())
k = [[0, ' '], [0, ' ']]
c = [[0, ' ']]
sum = 0
vehicles = []
for i in range(n):
	q = input().split()
	if q[0] == '1':
		k += [[int(q[1]), i + 1]]
	elif q[0] == '2':
		c += [[int(q[1]), i + 1]]
k.sort(key=lambda a: a[0])
c.sort(key=lambda a: a[0])
for i in range(n):
	if c[-1][0] > k[-1][0] + k[-2][0]:
		if v >= 2:
			add = c[-1][0]
			vehicles.append(c[-1][1])
			c.pop()
			v -= 2
		elif v >= 1:
			add = k[-1][0]
			vehicles.append(k[-1][1])
			k.pop()
			v -= 1
	elif v >= 1:
		add = k[-1][0]
		vehicles.append(k[-1][1])
		k.pop()
		v -= 1
	sum += add
	if v == 0:
		break
print(sum)
for i in vehicles:
	print(i, end=' ')


(n, v) = map(int, input().split())
l1 = []
l2 = []
for i in range(n):
	(t, x) = map(int, input().split())
	if t == 1:
		l1.append([x, i + 1])
	else:
		l2.append([x, i + 1])
l1.sort(reverse=True)
l2.sort(reverse=True)
s1 = [0]
s2 = [0]
for i in range(min(v, len(l1))):
	s1.append(s1[-1] + l1[i][0])
for i in range(min(int(v / 2), len(l2))):
	s2.append(s2[-1] + l2[i][0])
ans = 0
num = 0
for i in range(min(v, len(l1)) + 1):
	t = s1[i] + s2[min(len(l2), int((v - i) / 2))]
	if ans < t:
		num = i
		ans = t
print(ans)
print(' '.join(map(lambda x: str(x[1]), l1[0:num] + l2[0:min(len(l2), int((v - num) / 2))])))


(N, cap) = [int(_) for _ in input().split()]
one = []
two = []
for _ in range(N):
	(n, c) = [int(_) for _ in input().split()]
	if n == 1:
		one.append([c, _])
	else:
		two.append([c, _])
one.sort(reverse=True)
two.sort(reverse=True)
for i in range(1, len(one)):
	one[i][0] += one[i - 1][0]
for i in range(1, len(two)):
	two[i][0] += two[i - 1][0]
optimal = [0, 0, 0]
for i in range(cap + 1):
	if i > len(one):
		break
	j = min(len(two), (cap - i) // 2)
	total = (one[i - 1][0] if i >= 1 else 0) + (two[j - 1][0] if j >= 1 else 0)
	if total > optimal[0]:
		optimal[:] = (total, i, j)
print(optimal[0])
ret = []
for _ in range(optimal[1]):
	ret.append(str(one[_][1] + 1))
for _ in range(optimal[2]):
	ret.append(str(two[_][1] + 1))
print(' '.join(ret))


(n, v) = map(int, input().split())
selected = []
ones = []
twos = []
ans = 0
for i in range(1, n + 1):
	(t, p) = map(int, input().split())
	if t == 1:
		ones.append((p, i))
	if t == 2:
		twos.append((p, i))
ones.sort()
twos.sort()
num1 = len(ones)
num2 = len(twos)
last_one = None
while num1 + num2 > 0 and v > 0:
	if v == 1:
		if num1 == 0 and last_one is not None:
			(p, i) = twos[-1]
			if p > last_ans1:
				selected.remove(last_one)
				selected.append(i)
				ans += p - last_ans1
		elif num1 != 0:
			ans += ones[-1][0]
			selected.append(ones[-1][1])
		break
	if num1 == 0:
		num2 -= 1
		(p, i) = twos.pop()
		v -= 2
	elif num2 == 0:
		num1 -= 1
		(p, i) = ones.pop()
		v -= 1
	elif 2 * ones[-1][0] > twos[-1][0]:
		num1 -= 1
		(p, i) = ones.pop()
		v -= 1
		last_one = i
		last_ans1 = p
	else:
		num2 -= 1
		(p, i) = twos.pop()
		v -= 2
	ans += p
	selected.append(i)
print(ans)
print(' '.join([str(s) for s in selected]))


def solve(by_w, b, v):
	rem = min(v - 2 * b, len(by_w[1]))
	if rem < 0:
		return (-1, 0, 0)
	score = 0 if b == 0 else by_w[2][b - 1][0]
	if rem > 0:
		score += by_w[1][rem - 1][0]
	return (score, rem, b)

def main():
	(n, v) = map(int, input().split())
	by_w = [[] for _ in range(3)]
	for i in range(n):
		(t, p) = map(int, input().split())
		by_w[t].append((p, i + 1))
	(a, b) = (len(by_w[1]), len(by_w[2]))
	by_w[1].sort(reverse=True)
	by_w[2].sort(reverse=True)
	for i in range(1, a):
		by_w[1][i] = (by_w[1][i][0] + by_w[1][i - 1][0], by_w[1][i][1])
	for i in range(1, b):
		by_w[2][i] = (by_w[2][i][0] + by_w[2][i - 1][0], by_w[2][i][1])
	score = (-1, 0, 0)
	for i in range(b + 1):
		t = solve(by_w, i, v)
		score = max(score, t)
	inds = [by_w[1][i][1] for i in range(score[1])]
	inds += [by_w[2][i][1] for i in range(score[2])]
	inds.sort()
	print(score[0])
	print(' '.join((str(x) for x in inds)))
main()


(n, capacity) = map(int, input().split())
(kayaks, catamarans) = ([], [])
for i in range(n):
	(vehicle_type, vehicle_capacity) = map(int, input().split())
	l = kayaks if vehicle_type == 1 else catamarans
	l.append((vehicle_capacity, i + 1))
kayaks.sort(key=lambda item: item[0], reverse=True)
catamarans.sort(key=lambda item: item[0], reverse=True)
max_capacity = 0
kayaks_cap = [0]
catamarans_cap = [0]
for i in range(min(capacity, len(kayaks))):
	kayaks_cap.append(kayaks_cap[i] + kayaks[i][0])
for i in range(min(capacity // 2, len(catamarans))):
	catamarans_cap.append(catamarans_cap[i] + catamarans[i][0])
kayaks_idx = 0
catamarans_idx = 0
for (i, k) in enumerate(kayaks_cap):
	if i > capacity:
		break
	if k + catamarans_cap[min((capacity - i) // 2, len(catamarans_cap) - 1)] > max_capacity:
		max_capacity = k + catamarans_cap[min((capacity - i) // 2, len(catamarans_cap) - 1)]
		kayaks_idx = i
		catamarans_idx = min((capacity - i) // 2, len(catamarans_cap) - 1)
print(max_capacity)
for i in range(kayaks_idx):
	print(kayaks[i][1], end=' ')
for i in range(catamarans_idx):
	print(catamarans[i][1], end=' ')


(n, v) = map(int, input().split())
temp = {1: [], 2: []}
s = {1: [0], 2: [0]}
for i in range(n):
	(x, y) = map(int, input().split())
	temp[x].append([y, i + 1])
temp[1].sort(reverse=True)
temp[2].sort(reverse=True)
for i in range(min(v, len(temp[1]))):
	s[1].append(s[1][-1] + temp[1][i][0])
for i in range(min(v // 2, len(temp[2]))):
	s[2].append(s[2][-1] + temp[2][i][0])
ans = 0
num = 0
for i in range(min(v, len(temp[1])) + 1):
	t = s[1][i] + s[2][min(len(temp[2]), (v - i) // 2)]
	if ans < t:
		(num, ans) = (i, t)
print(ans)
for i in range(num):
	print(temp[1][i][1], end=' ')
for i in range(min(len(temp[2]), (v - num) // 2)):
	print(temp[2][i][1], end=' ')


(n, v) = map(int, input().split())
(baydarki, katamaran) = ([], [])
for i in range(n):
	(t, p) = map(int, input().split())
	if t == 1:
		baydarki.append([p, i + 1])
	else:
		katamaran.append([p, i + 1])
baydarki.sort(reverse=True)
katamaran.sort(reverse=True)
(load1, load2) = ([0], [0])
capacity = 0
for i in range(min(v, len(baydarki))):
	capacity += baydarki[i][0]
	load1.append(capacity)
capacity = 0
for i in range(min(v // 2, len(katamaran))):
	capacity += katamaran[i][0]
	load2.append(capacity)

def find_best_load():
	best = step = res = 0
	pos = min(v, len(baydarki)) + 1
	for i in range(pos):
		kat_posibilities = int((v - i) / 2)
		idx_best_katamarans = min(len(katamaran), kat_posibilities)
		best = load1[i] + load2[idx_best_katamarans]
		if best > res:
			res = best
			step = i
	return (res, step)

def display_solution(r, step):
	print(r)
	for i in range(step):
		print(baydarki[i][1], end=' ')
	katamaran_range = min(len(katamaran), int((v - step) / 2))
	for i in range(katamaran_range):
		print(katamaran[i][1], end=' ')
(r, s) = find_best_load()
display_solution(r, s)


(n, v) = map(int, input().split())
a = []
b = []
for i in range(n):
	(t, p) = map(int, input().split())
	if t == 1:
		a.append((i, p))
	else:
		b.append((i, p))
a = sorted(a, key=lambda x: -x[1])
b = sorted(b, key=lambda x: -x[1])
a_pos = -1
b_pos = -1
capacity = 0
while capacity < v:
	next_a = a[a_pos + 1][1] if a_pos + 1 < len(a) and capacity + 1 <= v else -1
	next_b = b[b_pos + 1][1] if b_pos + 1 < len(b) and capacity + 2 <= v else -1
	if next_a == -1 and next_b == -1:
		break
	if next_a > next_b / 2:
		a_pos += 1
		capacity += 1
	else:
		b_pos += 1
		capacity += 2
if capacity < v and a_pos > -1 and (b_pos + 1 < len(b)):
	if a[a_pos][1] < b[b_pos + 1][1]:
		a_pos -= 1
		b_pos += 1
print(sum([x[1] for x in a[:a_pos + 1]]) + sum([x[1] for x in b[:b_pos + 1]]))
for i in range(a_pos + 1):
	print(a[i][0] + 1)
for i in range(b_pos + 1):
	print(b[i][0] + 1)


kayak = []
catamaran = []
ans = []
line = input()
data = line.split()
n = int(data[0])
v = int(data[1])
for i in range(1, n + 1):
	line = input()
	data = line.split()
	type = data[0]
	if type == '1':
		kayak.append([int(data[1]), i])
	else:
		catamaran.append([int(data[1]), i])
len_k = len(kayak)
len_c = len(catamaran)
kayak.sort(key=lambda x: x[0], reverse=True)
catamaran.sort(key=lambda x: x[0], reverse=True)
num_k = 0
num_c = 0
capicity = 0
while v > 0 and (num_c != len_c or num_k != len_k):
	if num_k != len_k and (num_c == len_c or kayak[num_k][0] > catamaran[num_c][0] / 2):
		v -= 1
		capicity += kayak[num_k][0]
		ans.append(kayak[num_k][1])
		num_k += 1
	elif v >= 2:
		v -= 2
		capicity += catamaran[num_c][0]
		ans.append(catamaran[num_c][1])
		num_c += 1
	else:
		break
	if num_c == len_c and num_k == len_k:
		break
	if v == 1:
		if num_c != len_c and num_k != len_k:
			if kayak[num_k][0] + kayak[num_k - 1][0] < catamaran[num_c][0]:
				del ans[ans.index(kayak[num_k - 1][1])]
				v -= 1
				capicity -= kayak[num_k - 1][0]
				capicity += catamaran[num_c][0]
				ans.append(catamaran[num_c][1])
				num_c += 1
			else:
				v -= 1
				capicity += kayak[num_k][0]
				ans.append(kayak[num_k][1])
				num_k += 1
		elif num_k == len_k:
			if kayak[num_k - 1][0] < catamaran[num_c][0]:
				del ans[ans.index(kayak[num_k - 1][1])]
				v -= 1
				capicity -= kayak[num_k - 1][0]
				capicity += catamaran[num_c][0]
				ans.append(catamaran[num_c][1])
				num_c += 1
anstr = [str(x) for x in ans]
print(capicity)
print(' '.join(anstr))


(n, v) = map(int, input().split())
(kayaks, catamarans) = ([], [])
for i in range(n):
	(t, p) = map(int, input().split())
	if t == 1:
		kayaks.append([p, i + 1])
	else:
		catamarans.append([p, i + 1])
kayaks.sort(reverse=True)
catamarans.sort(reverse=True)
s_kayak = [0]
s_catamaran = [0]
for i in range(min(v, len(kayaks))):
	s_kayak.append(s_kayak[-1] + kayaks[i][0])
for i in range(min(int(v / 2), len(catamarans))):
	s_catamaran.append(s_catamaran[-1] + catamarans[i][0])
max_carry = 0
num = 0
for i in range(min(v, len(kayaks)) + 1):
	t = s_kayak[i] + s_catamaran[min(len(catamarans), int((v - i) / 2))]
	if max_carry < t:
		num = i
		max_carry = t
print(max_carry)
print(' '.join(map(lambda p: str(p[1]), kayaks[0:num] + catamarans[0:min(len(catamarans), int((v - num) / 2))])))


import sys
(n, v) = map(int, input().split())
kayak = []
catam = []
for i in range(0, n):
	nums = list(map(int, sys.stdin.readline().split()))
	if nums[0] == 1:
		kayak.append((nums[1], i + 1))
	else:
		catam.append((nums[1], i + 1))
kayak.sort(key=lambda pair: pair[0])
catam.sort(key=lambda pair: pair[0])
truck = []
while v > 0:
	if v == 1:
		if kayak:
			truck.append(kayak.pop())
		v -= 1
	elif not kayak and (not catam):
		v = 0
	elif not kayak:
		truck.append(catam.pop())
		v -= 2
	elif not catam:
		truck.append(kayak.pop())
		v -= 1
	elif len(kayak) == 1:
		if kayak[0][0] > catam[-1][0]:
			truck.append(kayak.pop())
			v -= 1
		else:
			truck.append(catam.pop())
			v -= 2
	elif kayak[-1][0] + kayak[-2][0] > catam[-1][0]:
		truck.append(kayak.pop())
		v -= 1
	else:
		truck.append(catam.pop())
		v -= 2
ans = 0
for i in truck:
	ans += i[0]
print(ans)
for i in truck:
	sys.stdout.write(str(i[1]) + ' ')


def main():
	(n, v) = map(int, input().split())
	kayak = list()
	k_add = kayak.append
	catamaran = list()
	c_add = catamaran.append
	for i in range(1, n + 1):
		(t, p) = map(int, input().split())
		pn = (p, i)
		if t == 1:
			k_add(pn)
		else:
			c_add(pn)
	catamaran.sort(reverse=True)
	last_catamaran = min(v >> 1, len(catamaran))
	kayak.sort()
	n_kayaks = len(kayak)
	first_kayak = max(0, n_kayaks - v + last_catamaran * 2)
	while first_kayak > 1 and last_catamaran > 0:
		pk = kayak[first_kayak - 1][0] + kayak[first_kayak - 2][0]
		pc = catamaran[last_catamaran - 1][0]
		if pc >= pk:
			break
		first_kayak -= 2
		last_catamaran -= 1
	capacity = 0
	choice = list()
	remember = choice.append
	for x in range(first_kayak, n_kayaks):
		(p, k) = kayak[x]
		capacity += p
		remember(k)
	for x in range(last_catamaran):
		(p, k) = catamaran[x]
		capacity += p
		remember(k)
	print(capacity)
	print(' '.join(map(str, choice)))
main()


(n, c) = map(int, input().split())
ones = []
twos = []
cnt = 0
for i in range(n):
	cnt += 1
	(x, y) = map(int, input().split())
	if x == 1:
		ones.append([y, cnt])
	else:
		twos.append([y, cnt])
ones.sort(key=lambda s: -s[0])
twos.sort(key=lambda s: -s[0])
sum = 0
pt_1 = 0
pt_2 = 0
ans = []
m1 = len(ones)
m2 = len(twos)
while c > 0:
	if pt_1 < m1:
		if pt_2 < m2:
			if pt_1 + 1 < m1:
				if ones[pt_1][0] + ones[pt_1 + 1][0] <= twos[pt_2][0] and c >= 2:
					sum += twos[pt_2][0]
					c -= 2
					ans.append(twos[pt_2][1])
					pt_2 += 1
				else:
					sum += ones[pt_1][0]
					c -= 1
					ans.append(ones[pt_1][1])
					pt_1 += 1
			elif ones[pt_1][0] < twos[pt_2][0] and c >= 2:
				sum += twos[pt_2][0]
				c -= 2
				ans.append(twos[pt_2][1])
				pt_2 += 1
			else:
				sum += ones[pt_1][0]
				c -= 1
				ans.append(ones[pt_1][1])
				pt_1 += 1
		else:
			c -= 1
			ans.append(ones[pt_1][1])
			sum += ones[pt_1][0]
			pt_1 += 1
	elif c >= 2:
		if pt_2 < m2:
			c -= 2
			sum += twos[pt_2][0]
			ans.append(twos[pt_2][1])
			pt_2 += 1
		else:
			break
	else:
		break
print(sum)
for i in ans:
	print(i, end=' ')


class Solution(object):

	def __init__(self):
		(n, v) = map(int, input().split())
		l1 = []
		l2 = []
		for i in range(n):
			(x, y) = map(int, input().split())
			if x == 1:
				l1.append((y, i + 1))
			else:
				l2.append((y, i + 1))
		l1.sort(reverse=True)
		l2.sort(reverse=True)
		s1 = [0]
		s2 = [0]
		for i in range(min(v, len(l1))):
			s1.append(s1[-1] + l1[i][0])
		for i in range(min(v // 2, len(l2))):
			s2.append(s2[-1] + l2[i][0])
		ans = idx1 = idx2 = 0
		for i in range(len(s1)):
			j = min(len(s2) - 1, (v - i) // 2)
			x = s1[i] + s2[j]
			if ans < x:
				ans = x
				idx1 = i
				idx2 = j
		print(f'{ans}')
		a = [l1[i][1] for i in range(idx1)] + [l2[i][1] for i in range(idx2)]
		for x in a:
			print(f'{x}', end=' ')
	pass

def main():
	Solution()
	pass
main()


__author__ = 'Eddie'
import sys

def get_filehandler(is_file):
	if is_file:
		return open(file='data')
	else:
		import sys
		return sys.stdin
fh = get_filehandler(is_file=False)
(n, v) = [int(value) for value in fh.readline().split()]
d = {'1': [], '2': []}
for _i in range(1, n + 1):
	(t, c) = fh.readline().split()
	d[t].append((int(c), str(_i)))
d['1'].sort()
d['2'].sort()
capacity = 0
num_v = []
last_k = None
while len(d['1']) > 1 and len(d['2']) > 0 and (v > 1):
	if d['1'][-1][0] + d['1'][-2][0] > d['2'][-1][0]:
		capacity += d['1'][-1][0] + d['1'][-2][0]
		num_v.append(d['1'][-1][1])
		num_v.append(d['1'][-2][1])
		last_k = (len(num_v) - 1, d['1'][-2][0])
		del d['1'][-2:]
	else:
		capacity += d['2'][-1][0]
		num_v.append(d['2'][-1][1])
		del d['2'][-1]
	v -= 2
while len(d['2']) > 0 and v > 1:
	capacity += d['2'][-1][0]
	num_v.append(d['2'][-1][1])
	del d['2'][-1]
	v -= 2
if v == 1:
	if last_k is not None and len(d['2']) > 0:
		d_1 = 0
		if len(d['1']) > 0:
			d_1 = d['1'][-1][0]
		if last_k[1] + d_1 < d['2'][-1][0]:
			del num_v[last_k[0]]
			v -= 1
			capacity -= last_k[1]
			capacity += d['2'][-1][0]
			num_v.append(d['2'][-1][1])
while len(d['1']) > 0 and v > 0:
	capacity += d['1'][-1][0]
	num_v.append(d['1'][-1][1])
	del d['1'][-1]
	v -= 1
print(capacity)
print(' '.join(num_v))


(n, v) = map(int, input().split())
(p, t) = ([], [])
for i in range(1, n + 1):
	(a, b) = map(int, input().split())
	t.append((b * (3 - a), a, b, i))
t.sort(reverse=True)
a = b = i = 0
while i < n and a < v:
	a += t[i][1]
	b += t[i][2]
	p.append(t[i][3])
	i += 1
if a > v:
	(i, j, k) = (i - 1, i - 2, i)
	while j >= 0 and t[j][1] > 1:
		j -= 1
	while k < n and t[k][1] > 1:
		k += 1
	if j >= 0:
		if k < n:
			if t[j][2] + t[k][2] > t[i][2]:
				p[i] = t[k][3]
				b += t[k][2] - t[i][2]
			else:
				p.pop(j)
				b -= t[j][2]
		elif t[j][2] > t[i][2]:
			p.pop()
			b -= t[i][2]
		else:
			p.pop(j)
			b -= t[j][2]
	elif k < n:
		p[i] = t[k][3]
		b += t[k][2] - t[i][2]
	else:
		p.pop()
		b -= t[i][2]
print(b)
print(' '.join(map(str, p)))


(n, v) = map(int, input().split())
temp1 = []
temp2 = []
for i in range(n):
	(t, x) = map(int, input().split())
	if t == 1:
		temp1.append([x, i + 1])
	else:
		temp2.append([x, i + 1])
temp1.sort(reverse=True)
temp2.sort(reverse=True)
s1 = [0]
s2 = [0]
for i in range(min(v, len(temp1))):
	s1.append(s1[-1] + temp1[i][0])
for i in range(min(int(v / 2), len(temp2))):
	s2.append(s2[-1] + temp2[i][0])
num = 0
ans = 0
for i in range(min(v, len(temp1)) + 1):
	s = s1[i] + s2[min(len(temp2), int((v - i) / 2))]
	if ans < s:
		(num, ans) = (i, s)
print(ans)
for i in range(num):
	print(temp1[i][1], end=' ')
for i in range(min(len(temp2), int((v - num) / 2))):
	print(temp2[i][1], end=' ')


(n, v) = map(int, input().split())
V = [[], []]
for i in range(n):
	(t, s) = map(int, input().split())
	V[t - 1].append((s, i + 1))
V[0].append((-1000000, 0))
V[0].append((-1000000, 0))
V[1].append((-1000000, 0))
V[0].sort()
V[1].sort()
V[0] = V[0][::-1]
V[1] = V[1][::-1]
cnt0 = 0
cnt1 = 0
while v >= 2:
	s1 = V[0][cnt0][0] + V[0][cnt0 + 1][0]
	s2 = V[1][cnt1][0]
	if s1 < 0 and s2 < 0:
		break
	if s1 > s2:
		cnt0 += 2
	else:
		cnt1 += 1
	v -= 2
if v >= 1:
	if V[1][cnt1][0] > 0 and cnt0 > 0 and (V[1][cnt1][0] > V[0][cnt0 - 1][0] + V[0][cnt0][0]) and (V[1][cnt1][0] > V[0][cnt0 - 1][0]):
		cnt1 += 1
		cnt0 -= 1
	elif V[0][cnt0][0] > 0:
		cnt0 += 1
Sum = 0
No = []
for i in range(cnt0):
	Sum += V[0][i][0]
	No.append(V[0][i][1])
for i in range(cnt1):
	Sum += V[1][i][0]
	No.append(V[1][i][1])
No.sort()
print(Sum)
for i in No:
	print(i, end=' ')
print()


(n, v) = map(int, input().split())
kayaks = []
catamarans = []
for i in range(n):
	(t, p) = map(int, input().split())
	waterbone = kayaks if t == 1 else catamarans
	waterbone.append((p, i + 1))
kayaks.sort(reverse=True)
catamarans.sort(reverse=True)
capacity = 0
vehicles = []
kayak = 0
catamaran = 0
nb_kayaks = len(kayaks)
nb_catamarans = len(catamarans)
if v % 2 == 1 and nb_kayaks > 0:
	(c, k) = kayaks[0]
	capacity += c
	vehicles.append(k)
	kayak = 1
while 1:
	if v - (kayak + catamaran * 2) < 2 or (kayak >= nb_kayaks and catamaran >= nb_catamarans):
		break
	if catamaran < nb_catamarans:
		(c, i) = catamarans[catamaran]
		if kayak < nb_kayaks:
			(k1, ik1) = kayaks[kayak]
			if kayak + 1 < nb_kayaks:
				(k2, ik2) = kayaks[kayak + 1]
				if c > k1 + k2:
					vehicles.append(i)
					capacity += c
					catamaran += 1
				else:
					vehicles.append(ik1)
					vehicles.append(ik2)
					capacity += k1 + k2
					kayak += 2
			elif c > k1:
				vehicles.append(i)
				capacity += c
				catamaran += 1
			else:
				vehicles.append(ik1)
				capacity += k1
				kayak += 1
		else:
			capacity += c
			vehicles.append(i)
			catamaran += 1
	else:
		(k1, ik1) = kayaks[kayak]
		if kayak + 1 < nb_kayaks:
			(k2, ik2) = kayaks[kayak + 1]
			capacity += k1 + k2
			vehicles.append(ik1)
			vehicles.append(ik2)
			kayak += 2
		else:
			capacity += k1
			vehicles.append(ik1)
			kayak += 1
print(capacity)
print(*vehicles, sep=' ')


(n, v) = (int(x) for x in input().split())
(a1, a2) = ([], [])
for i in range(n):
	(t, p) = (int(x) for x in input().split())
	(a1 if t == 1 else a2).append((p, i + 1))
a1.sort()
a2.sort()
c = 0
z = []

def pop(t):
	global c, v
	a = a1 if t == 1 else a2
	c += a[-1][0]
	z.append(a[-1][1])
	a.pop()
	v -= t
while True:
	if v >= 1 and (v % 2 == 1 or not a2) and a1:
		pop(1)
	elif v >= 2 and len(a1) >= 2 and a2 and (a1[-1][0] + a1[-2][0] >= a2[-1][0]):
		pop(1)
		pop(1)
	elif v >= 1 and a1 and a2 and (a1[-1][0] >= a2[-1][0]):
		pop(1)
	elif v >= 2 and a2:
		pop(2)
	else:
		break
print(c)
print(' '.join((str(x) for x in z)))


m = lambda : map(int, input().split())
[n, v] = m()
(fi, se) = ([], [])
for i in range(1, int(n) + 1):
	[ti, pi] = m()
	if ti == 1:
		fi.append([i, pi])
	else:
		se.append([i, pi])
fi.sort(key=lambda x: x[1], reverse=True)
se.sort(key=lambda x: x[1], reverse=True)
for i in range(1, len(fi)):
	fi[i][1] += fi[i - 1][1]
for i in range(1, len(se)):
	se[i][1] += se[i - 1][1]
(s, s1, s2) = (0, 0, 0)
p = 0
for i in range(v + 1):
	r = 0
	if i > len(fi):
		break
	a = min((v - i) / 2, len(se))
	a = int(a)
	if i > 0:
		r += fi[i - 1][1]
	if a > 0:
		r += se[a - 1][1]
	if s < r:
		s = r
		s1 = i
		s2 = a
print(s)
for i in range(s1):
	print(fi[i][0], end=' ')
for i in range(int(s2)):
	print(se[i][0], end=' ')


import os
import sys
from io import BytesIO, IOBase
import math
from decimal import *
from collections import defaultdict
getcontext().prec = 25
MOD = pow(10, 9) + 7
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, v) = map(int, input().split(' '))
asdsa = False
k = []
c = []
for i in range(n):
	(t, val) = map(int, input().split(' '))
	if t == 1:
		k.append((val, i + 1))
	else:
		c.append((val, i + 1))
k.sort()
c.sort()
ans = []
i = len(k) - 1
j = len(c) - 1
while v:
	if v == 1:
		if i >= 0:
			ans.append(k[i])
			v -= 1
			i -= 1
			break
		else:
			break
	if i < 0 and j < 0:
		break
	if i >= 0:
		if j >= 0:
			if k[i][0] >= c[j][0]:
				v -= 1
				ans.append(k[i])
				i -= 1
			elif i >= 1:
				if k[i][0] + k[i - 1][0] > c[j][0]:
					ans.append(k[i])
					ans.append(k[i - 1])
					i -= 2
					v -= 2
				else:
					v -= 2
					ans.append(c[j])
					j -= 1
			else:
				v -= 2
				ans.append(c[j])
				j -= 1
		else:
			ans.append(k[i])
			i -= 1
			v -= 1
	elif j >= 0:
		ans.append(c[j])
		v -= 2
		j -= 1
	else:
		break
to_skip = []
while i <= len(k) - 2 and j >= 0:
	if k[i + 1][0] + k[i + 2][0] < c[j][0]:
		to_skip.append(k[i + 1][1])
		to_skip.append(k[i + 2][1])
		ans.append(c[j])
		j -= 1
		i += 2
	else:
		break
s = 0
an = []
for i in ans:
	if i[1] not in to_skip:
		s += i[0]
		an.append(i[1])
print(s)
print(*an)


import os
import sys
from io import BytesIO, IOBase

def main():
	(n, v) = map(int, input().split())
	(a, b) = ([], [])
	for i in range(n):
		(t, p) = map(int, input().split())
		if t == 1:
			a.append([p, i + 1])
		else:
			b.append([p, i + 1])
	a.sort()
	a = a[::-1]
	b.sort()
	b = b[::-1]
	(na, nb) = (len(a), len(b))
	(l, r) = (0, 0)
	ans = []
	val = 0
	while v:
		if v >= 2:
			if l < na - 1 and r < nb:
				if a[l][0] > b[r][0]:
					val += a[l][0]
					v -= 1
					ans.append(a[l][1])
					l += 1
				elif a[l][0] + a[l + 1][0] > b[r][0]:
					val += a[l][0]
					v -= 1
					ans.append(a[l][1])
					l += 1
				else:
					val += b[r][0]
					ans.append(b[r][1])
					v -= 2
					r += 1
			elif l == na - 1 and r < nb:
				if a[l][0] > b[r][0]:
					val += a[l][0]
					v -= 1
					ans.append(a[l][1])
					l += 1
				else:
					val += b[r][0]
					v -= 2
					ans.append(b[r][1])
					r += 1
			elif l < na:
				val += a[l][0]
				v -= 1
				ans.append(a[l][1])
				l += 1
			elif r < nb:
				val += b[r][0]
				ans.append(b[r][1])
				v -= 2
				r += 1
			else:
				break
		elif l < na:
			ans.append(a[l][1])
			val += a[l][0]
			v -= 1
			l += 1
		else:
			break
	print(val)
	print(*ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import math as mt
import sys, string, bisect
input = sys.stdin.readline
from collections import deque
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
I = lambda : int(input())
(n, v) = M()
k = []
c = []
for i in range(n):
	(t, cap) = M()
	if t == 1:
		k.append((cap, i + 1))
	else:
		c.append((cap, i + 1))
k.sort(reverse=True, key=lambda x: x[0])
c.sort(reverse=True, key=lambda x: x[0])
lorry = v
ans = 0
a = []
i = 0
j = 0
while (lorry > 1 and i < len(c)) and j < len(k) - 1:
	if lorry >= 2:
		if c[i][0] >= k[j][0] + k[j + 1][0]:
			lorry -= 2
			ans += c[i][0]
			a.append(c[i][1])
			i += 1
		else:
			lorry -= 2
			ans += k[j][0] + k[j + 1][0]
			a.append(k[j][1])
			a.append(k[j + 1][1])
			j += 2
while i < len(c) and lorry >= 2:
	ans += c[i][0]
	a.append(c[i][1])
	lorry -= 2
	i += 1
while j < len(k) and lorry > 0:
	ans += k[j][0]
	a.append(k[j][1])
	lorry -= 1
	j += 1
if i < len(c):
	if j - 1 >= 0 and k[j - 1][0] < c[i][0] and (lorry + 1 >= 2):
		lorry += 1
		ans -= k[j - 1][0]
		a.remove(k[j - 1][1])
		a.append(c[i][1])
		ans += c[i][0]
		lorry -= 2
		j -= 1
		i += 1
	elif j >= 2 and k[j - 1][0] + k[j - 2][0] < c[i][0] and (lorry + 2 >= 2):
		lorry += 2
		ans -= k[j - 1][0]
		ans -= k[j - 2][0]
		a.remove(k[j - 1][1])
		a.remove(k[j - 2][1])
		j -= 2
		a.append(c[i][1])
		ans += c[i][0]
		lorry -= 2
		i += 1
print(ans)
print(*a)


import sys
input = sys.stdin.readline
(n, v) = map(int, input().split())
(o, t) = ([], [])
for i in range(n):
	(x, y) = map(int, input().split())
	if x == 1:
		o.append((y, i + 1))
	else:
		t.append((y, i + 1))
o.sort(reverse=True)
t.sort(reverse=True)
if len(o) == 0:
	ans = 0
	f = []
	for i in range(len(t)):
		if (i + 1) * 2 <= v:
			ans += t[i][0]
			f.append(t[i][1])
	print(ans)
	print(*f)
else:
	p = [o[0][0]]
	for i in range(1, len(o)):
		p.append(p[-1] + o[i][0])
	ans = p[min(len(p) - 1, v - 1)]
	s = 0
	ind = -1
	for i in range(len(t)):
		if (i + 1) * 2 > v:
			break
		s += t[i][0]
		if (i + 1) * 2 != v:
			if s + p[min(len(p) - 1, v - (i + 1) * 2 - 1)] > ans:
				ans = s + p[min(len(p) - 1, v - (i + 1) * 2 - 1)]
				ind = i
		elif s > ans:
			ans = max(ans, s)
			ind = i
	print(ans)
	f = []
	for i in range(ind + 1):
		f.append(t[i][1])
	for i in range(min(len(o), v - (ind + 1) * 2)):
		f.append(o[i][1])
	print(*f)


(n, v) = map(int, input().split())
tp = []
for i in range(n):
	(ti, pi) = map(int, input().split())
	tp.append((ti, pi, i + 1))
tp.sort(key=lambda _: -_[1] / _[0])
(numbers, v_current, quality) = ([], 0, 0)
last_ones = (-2, -1)
for (i, tpi) in enumerate(tp):
	if v_current + tpi[0] <= v:
		v_current += tpi[0]
		quality += tpi[1]
		numbers.append(tpi[2])
		if tpi[0] == 1:
			last_ones = (last_ones[1], i)
if v_current == v:
	(numbers2, v_current2, quality2) = ([], 0, 0)
	for (i, tpi) in enumerate(tp):
		if v_current2 + tpi[0] <= v and (tpi[0] != 1 or i < last_ones[0]):
			v_current2 += tpi[0]
			quality2 += tpi[1]
			numbers2.append(tpi[2])
	if quality2 > quality:
		numbers = numbers2
		quality = quality2
if v_current + 1 == v:
	(numbers3, v_current3, quality3) = ([], 0, 0)
	for (i, tpi) in enumerate(tp):
		if v_current3 + tpi[0] <= v and (tpi[0] != 1 or i < last_ones[1]):
			v_current3 += tpi[0]
			quality3 += tpi[1]
			numbers3.append(tpi[2])
	if quality3 > quality:
		numbers = numbers3
		quality = quality3
print(quality)
print(' '.join(map(str, numbers)))


def print_v(v):
	print(v, eval(v))
(n, v) = map(int, input().split())
vehicle1 = []
vehicle2 = []
for i in range(n):
	(t, p) = map(int, input().split())
	if t == 1:
		vehicle1.append((p, i + 1))
	else:
		vehicle2.append((p, i + 1))
vehicle1.sort(key=lambda x: x[0], reverse=True)
vehicle2.sort(key=lambda x: x[0], reverse=True)
index1 = 0
index2 = 0
current_v = 0
current_result = 0
numbers = []
while True:
	if v - current_v >= 2:
		if index2 < len(vehicle2) or index1 + 1 < len(vehicle1):
			if index2 < len(vehicle2) and index1 + 1 < len(vehicle1):
				if vehicle2[index2][0] > vehicle1[index1][0] + vehicle1[index1 + 1][0]:
					numbers.append((vehicle2[index2][0], vehicle2[index2][1], 2))
					index2 += 1
					current_v += 2
				else:
					numbers.append((vehicle1[index1][0], vehicle1[index1][1], 1))
					numbers.append((vehicle1[index1 + 1][0], vehicle1[index1 + 1][1], 1))
					index1 += 2
					current_v += 2
			else:
				if index2 < len(vehicle2):
					numbers.append((vehicle2[index2][0], vehicle2[index2][1], 2))
					index2 += 1
					current_v += 2
				if index1 + 1 < len(vehicle1):
					numbers.append((vehicle1[index1][0], vehicle1[index1][1], 1))
					numbers.append((vehicle1[index1 + 1][0], vehicle1[index1 + 1][1], 1))
					index1 += 2
					current_v += 2
		else:
			break
	else:
		break

def sum_numbers(numbers):
	if len(numbers) == 0:
		return 0
	result = 0
	for item in numbers:
		result += item[0]
	return result
if index1 < len(vehicle1) and v - current_v >= 1:
	numbers.append((vehicle1[index1][0], vehicle1[index1][1], 1))
	current_v += 1
is_1_in_numbers = False
is_1_in_numbers_twice = False
counter = 0
for item in numbers:
	if item[-1] == 1:
		is_1_in_numbers = True
		counter += 1
		if counter == 2:
			is_1_in_numbers_twice = True
			break
if v - current_v == 1 and index2 < len(vehicle2) and is_1_in_numbers:
	temp_numbers = numbers.copy()
	for i in range(len(temp_numbers) - 1, -1, -1):
		if temp_numbers[i][-1] == 1:
			del temp_numbers[i]
			break
	temp_numbers.append((vehicle2[index2][0], vehicle2[index2][1], 2))
	if sum_numbers(temp_numbers) > sum_numbers(numbers):
		numbers = temp_numbers
elif v - current_v == 0 and index2 < len(vehicle2) and is_1_in_numbers_twice:
	temp_numbers = numbers.copy()
	counter = 0
	for i in range(len(temp_numbers) - 1, -1, -1):
		if temp_numbers[i][-1] == 1:
			del temp_numbers[i]
			counter += 1
			if counter == 2:
				break
	temp_numbers.append((vehicle2[index2][0], vehicle2[index2][1], 2))
	if sum_numbers(temp_numbers) > sum_numbers(numbers):
		numbers = temp_numbers
numbers.sort(key=lambda x: x[1])
print(sum_numbers(numbers))
for item in numbers:
	print(item[1])


def solve(choices, length, capacity_limit):
	rem = min(capacity_limit - 2 * length, len(choices[1]))
	if rem < 0:
		return (-1, 0, 0)
	score = 0 if length == 0 else choices[2][length - 1][0]
	if rem > 0:
		score += choices[1][rem - 1][0]
	return (score, rem, length)
(quantity, capacity_limit) = map(int, input().split())
choices = [[] for _ in range(3)]
for i in range(quantity):
	(choice, capacity) = map(int, input().split())
	choices[choice].append((capacity, i + 1))
(length_choice_1, length_choice_2) = (len(choices[1]), len(choices[2]))
choices[1].sort(reverse=True)
choices[2].sort(reverse=True)
for i in range(1, length_choice_1):
	choices[1][i] = (choices[1][i][0] + choices[1][i - 1][0], choices[1][i][1])
for i in range(1, length_choice_2):
	choices[2][i] = (choices[2][i][0] + choices[2][i - 1][0], choices[2][i][1])
score = (-1, 0, 0)
for i in range(length_choice_2 + 1):
	choice = solve(choices, i, capacity_limit)
	score = max(score, choice)
indices = [choices[1][i][1] for i in range(score[1])]
indices += [choices[2][i][1] for i in range(score[2])]
indices.sort()
print(score[0])
print(' '.join((str(x) for x in indices)))


kk = lambda : map(int, input().split())
ll = lambda : list(kk())

def pop(ls):
	if not ls:
		return (0, -1)
	return ls.pop(-1)

def pop1():
	(v, i) = pop(l1)
	(v2, i2) = pop(l1)
	return (v + v2, i, i2)

def pop2():
	return pop(l2)
(n, v) = kk()
(l1, l2) = ([], [])
for i in range(n):
	(t, k) = kk()
	if t == 1:
		l1.append((k, i + 1))
	else:
		l2.append((k, i + 1))
l1.sort()
l2.sort()
total = 0
printed = []
if v % 2:
	(v1, i11) = pop(l1)
	total += v1
	printed.append(i11)
	v -= 1
(v1, i11, i12) = pop1()
(v2, i2) = pop2()
while v > 0 and (v1 > 0 or v2 > 0):
	if v1 < v2:
		total += v2
		printed.append(i2)
		(v2, i2) = pop2()
	else:
		total += v1
		printed.extend([i11, i12])
		(v1, i11, i12) = pop1()
	v -= 2
print(total)
print(' '.join([str(p) for p in printed if p != -1]))


R = lambda : map(int, input().split())
(n, v) = R()
(k, c) = ([], [])
for i in range(n):
	(t, a) = R()
	if t == 1:
		k += [[a, i + 1]]
	else:
		c += [[a, i + 1]]
k.sort(reverse=True)
c.sort(reverse=True)
sum = 0
klen = len(k)
clen = len(c)
y = min(klen, v)
for i in range(1, klen):
	k[i][0] += k[i - 1][0]
for i in range(1, clen):
	c[i][0] += c[i - 1][0]
if klen >= v and v > 0:
	ans = k[v - 1][0]
elif klen > 0 and v > 0:
	ans = k[klen - 1][0]
else:
	ans = 0
j = int((v - y) / 2)
if clen > 0:
	if j > 0 and j < clen:
		ans += c[j - 1][0]
	elif j > 0:
		ans += c[clen - 1][0]
		j = clen
	if 2 * j + y == v - 1 and j < clen:
		if y > 1 and ans <= c[j][0] + k[y - 2][0]:
			ans = c[j][0] + k[y - 2][0]
			(j, y) = (j + 1, y - 1)
		elif y == 1 and ans <= c[j][0]:
			ans = c[j][0]
			(y, j) = (0, j + 1)
	while y > 2 and j < clen and (ans <= c[j][0] + k[y - 3][0]):
		ans = c[j][0] + k[y - 3][0]
		(j, y) = (j + 1, y - 2)
	if y == 2 and j < clen and (ans <= c[j][0]):
		ans = c[j][0]
		(y, j) = (0, j + 1)
print(ans)
s = ''
for i in range(y):
	s += str(k[i][1]) + ' '
for i in range(j):
	s += str(c[i][1]) + ' '
print(s)


import sys
import operator
KAYAK_VOLUME = 1
CATAMARAN_VOLUME = 2

def main():
	kayaks = []
	catamarans = []
	(num_vehicles, volume) = map(int, sys.stdin.readline().strip().split())
	for i in range(1, num_vehicles + 1):
		(vehicle_type, capacity) = map(int, sys.stdin.readline().strip().split())
		if vehicle_type == 1:
			kayaks.append((i, capacity))
		else:
			catamarans.append((i, capacity))
	kayaks.sort(key=operator.itemgetter(1), reverse=True)
	catamarans.sort(key=operator.itemgetter(1), reverse=True)
	vehicle_numbers = []
	carried_capacity = 0
	num_kayaks = len(kayaks)
	num_catamarans = len(catamarans)
	carried_kayaks = 0
	carried_catamarans = 0
	free_space = volume
	while carried_kayaks < num_kayaks and free_space >= KAYAK_VOLUME or (carried_catamarans < num_catamarans and free_space >= CATAMARAN_VOLUME):
		if (free_space % 2 or carried_catamarans == num_catamarans) and carried_kayaks < num_kayaks:
			kayak = kayaks[carried_kayaks:carried_kayaks + 1]
			carried_kayaks += 1
			free_space -= KAYAK_VOLUME
			carried_capacity += kayak[0][1]
			vehicle_numbers.append(kayak[0][0])
		else:
			catamaran = catamarans[carried_catamarans:carried_catamarans + 1]
			if carried_kayaks < num_kayaks:
				kayak = kayaks[carried_kayaks:carried_kayaks + 2]
				if sum((k[1] for k in kayak)) > catamaran[0][1]:
					carried_kayaks += len(kayak)
					free_space -= len(kayak) * KAYAK_VOLUME
					carried_capacity += sum((k[1] for k in kayak))
					vehicle_numbers.extend((k[0] for k in kayak))
					continue
			carried_catamarans += 1
			free_space -= CATAMARAN_VOLUME
			carried_capacity += catamaran[0][1]
			vehicle_numbers.append(catamaran[0][0])
	sys.stdout.write(str(carried_capacity) + '\n')
	sys.stdout.write(' '.join(map(str, vehicle_numbers)) + '\n')
main()


r = lambda : map(int, input().split())
[n, v] = r()
t = []
o = []
for i in range(n):
	[tp, p] = r()
	if tp == 1:
		o += [[p, i]]
	else:
		t += [[p, i]]
t.sort(reverse=True)
o.sort(reverse=True)
nt = len(t)
no = len(o)
for i in range(1, nt):
	t[i][0] += t[i - 1][0]
for i in range(1, no):
	o[i][0] += o[i - 1][0]
a = [0, 0, 0]
for i in range(v + 1):
	if i > no:
		break
	j = min(nt, (v - i) // 2)
	r = 0
	if i:
		r += o[i - 1][0]
	if j:
		r += t[j - 1][0]
	a = max(a, [r, i, j])
print(a[0])
for i in range(a[1]):
	print(o[i][1] + 1)
for i in range(a[2]):
	print(t[i][1] + 1)


def main():
	(n, v) = map(int, input().split())
	k = []
	c = []
	for i in range(n):
		(t, p) = map(int, input().split())
		if t == 1:
			k.append([p, i + 1])
		else:
			c.append([p, i + 1])
	k.sort(reverse=True)
	c.sort(reverse=True)
	sk = [0]
	sc = [0]
	for i in range(min(v, len(k))):
		sk.append(sk[-1] + k[i][0])
	for i in range(min(int(v / 2), len(c))):
		sc.append(sc[-1] + c[i][0])
	ans = 0
	num = 0
	for i in range(min(v, len(k)) + 1):
		t = sk[i] + sc[min(int((v - i) / 2), len(c))]
		if ans < t:
			num = i
			ans = t
	print(ans)
	answer = []
	for i in range(num):
		answer.append(k[i][1])
	for i in range(min(int((v - num) / 2), len(c))):
		answer.append(c[i][1])
	print(' '.join((str(x) for x in answer)))
main()


import heapq
(n, v) = [int(i) for i in input().split()]
a = []
bai = []
kat = []
for i in range(n):
	t = [int(j) for j in input().split()]
	if t[0] == 1:
		bai.append((-t[1], str(i + 1)))
	else:
		kat.append((-t[1], str(i + 1)))
bai.sort(key=lambda i: i[0])
kat.sort(key=lambda i: i[0])
g = 0
bi = 0
ki = 0
if v % 2 == 1:
	if bi < len(bai) > 0:
		a.append(bai[bi][1])
		g = g + bai[bi][0]
		bi = bi + 1
	v = v - 1
if (len(bai) - bi) % 2 == 1:
	bai.append((0, 0))
while v > 0 and bi < len(bai) and (ki < len(kat)):
	if bai[bi][0] + bai[bi + 1][0] < kat[ki][0]:
		g = g + bai[bi][0] + bai[bi + 1][0]
		a.append(bai[bi][1])
		a.append(bai[bi + 1][1])
		bi = bi + 2
		v = v - 2
	else:
		g = g + kat[ki][0]
		a.append(kat[ki][1])
		ki = ki + 1
		v = v - 2
if len(bai) > bi:
	while v > 0 and len(bai) > bi:
		g = g + bai[bi][0] + bai[bi + 1][0]
		a.append(bai[bi][1])
		a.append(bai[bi + 1][1])
		bi = bi + 2
		v = v - 2
else:
	while v > 0 and len(kat) > ki:
		g = g + kat[ki][0]
		a.append(kat[ki][1])
		ki = ki + 1
		v = v - 2
print(-g)
for t in a:
	if t != 0:
		print(t)


(n, v) = map(int, input().split())
ba = []
ka = []
for i in range(n):
	(t, p) = map(int, input().split())
	if t == 1:
		ba.append([i + 1, p])
	else:
		ka.append([i + 1, p])
ba.sort(key=lambda x: x[1], reverse=True)
ka.sort(key=lambda x: x[1], reverse=True)
ba_pos = -1
ka_pos = -1
w = 0
while w < v:
	ba_g = -1
	if ba_pos + 1 < len(ba) and w + 1 <= v:
		ba_g = ba[ba_pos + 1][1]
	ka_g = -1
	if ka_pos + 1 < len(ka) and w + 2 <= v:
		ka_g = ka[ka_pos + 1][1]
	if ba_g == -1 and ka_g == -1:
		break
	if ba_g > ka_g / 2:
		ba_pos += 1
		w += 1
	else:
		ka_pos += 1
		w += 2
if v - w == 1:
	if ba_pos > -1 and ka_pos + 1 < len(ka):
		if ba[ba_pos][1] < ka[ka_pos + 1][1]:
			ba_pos -= 1
			ka_pos += 1
			w += 1
res = ba[:ba_pos + 1] + ka[:ka_pos + 1]
g = sum([r[1] for r in res])
print(g)
print(' '.join([str(r[0]) for r in res]))


def merge_sort_recursive(arr):
	if len(arr) <= 1:
		return arr
	middle = len(arr) // 2
	left = merge_sort_recursive(arr[:middle])
	right = merge_sort_recursive(arr[middle:])
	i = j = 0
	for k in range(len(arr)):
		if j == len(right) or (i < len(left) and left[i] < right[j]):
			arr[k] = left[i]
			i += 1
		else:
			arr[k] = right[j]
			j += 1
	return arr

def merge_sort(arr, reverse=False):
	arr_sorted = merge_sort_recursive(arr)
	if reverse:
		arr_sorted.reverse()
	for i in range(len(arr)):
		arr[i] = arr_sorted[i]

def move(boat_type_inner):
	global max_carrying, k_i, c_i, volume
	if boat_type_inner == 1:
		max_carrying += kayaks[k_i][0]
		boats.append(kayaks[k_i][1])
		k_i += 1
		volume -= 1
	else:
		max_carrying += catamarans[c_i][0]
		boats.append(catamarans[c_i][1])
		c_i += 1
		volume -= 2
(n, volume) = map(int, input().split())
max_carrying = 0
boats = []
kayaks = []
catamarans = []
for i in range(n):
	(boat_type, boat_carrying) = map(int, input().split())
	if boat_type == 1:
		kayaks.append((boat_carrying, i + 1))
	else:
		catamarans.append((boat_carrying, i + 1))
k_len = len(kayaks)
c_len = len(catamarans)
k_i = 0
c_i = 0
kayaks.sort(reverse=True)
catamarans.sort(reverse=True)
while True:
	if volume >= 1 and (volume % 2 == 1 or c_i == c_len) and (k_i < k_len):
		move(1)
	elif volume >= 2 and k_i + 1 < k_len and (c_i < c_len) and (kayaks[k_i][0] + kayaks[k_i + 1][0] >= catamarans[c_i][0]):
		move(1)
		move(1)
	elif volume >= 1 and k_i < k_len and (c_i < c_len) and (kayaks[k_i][0] >= catamarans[c_i][0]):
		move(1)
	elif volume >= 2 and c_i < c_len:
		move(2)
	else:
		break
print(str(max_carrying), ' '.join(map(str, boats)), sep='\n')


(n, v) = map(int, input().split())
boat = []
for i in range(n):
	boat.append(list(map(int, input().split())))
	boat[i].append(i + 1)
boat1 = [b for b in boat if b[0] == 1]
boat2 = [b for b in boat if b[0] == 2]
boat1.sort(key=lambda x: x[1], reverse=True)
boat2.sort(key=lambda x: x[1], reverse=True)
(ans, res) = (0, '')
(i, j) = (0, 0)
if len(boat1) <= v:
	ans += sum((b[1] for b in boat1))
	i = len(boat1)
else:
	ans += sum((b[1] for b in boat1[:v]))
	i = v
if v - len(boat1) >= len(boat2) * 2:
	ans += sum((b[1] for b in boat2))
	j = len(boat2)
else:
	ans += sum((b[1] for b in boat2[:(v - i) // 2]))
	j = (v - i) // 2
if i + j * 2 == v - 1 and i > 0 and (j < len(boat2)):
	if boat1[i - 1][1] < boat2[j][1]:
		ans += boat2[j][1] - boat1[i - 1][1]
		i -= 1
		j += 1
while i > 1 and j < len(boat2):
	if boat1[i - 1][1] + boat1[i - 2][1] < boat2[j][1]:
		ans += boat2[j][1] - boat1[i - 1][1] - boat1[i - 2][1]
		i -= 2
		j += 1
	else:
		break
print(ans)
temp = [v[2] for v in boat1[:i]]
res += ' '.join(list(map(str, temp)))
if res:
	res += ' '
temp = [v[2] for v in boat2[:j]]
res += ' '.join(list(map(str, temp)))
print(res)


import os, sys
from io import BytesIO, IOBase

def main():
	(n, v) = map(int, input().split())
	(on1, tw1) = ([], [])
	for i in range(n):
		(x1, x2) = map(int, input().split())
		if x1 == 1:
			on1.append((x2, i + 1))
		else:
			tw1.append((x2, i + 1))
	(on1.sort(key=lambda zzz: zzz[0]), tw1.sort(key=lambda zzz: zzz[0]))
	(on, tw) = ([0], [0])
	for i in range(len(on1)):
		on.append(on1[-i - 1][0] + on[i])
	for i in range(len(tw1)):
		tw.append(tw1[-i - 1][0] + tw[i])
	(ans, ind) = (0, 0)
	for i in range(min(v // 2, len(tw1)), -1, -1):
		z = tw[i] + on[min(len(on1), v - 2 * i)]
		if ans < z:
			(ans, ind) = (z, i)
	print(ans)
	for i in range(ind):
		print(tw1[-i - 1][1], end=' ')
	for i in range(min(v - 2 * ind, len(on1))):
		print(on1[-i - 1][1], end=' ')
	print('')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
(n, v) = sys.stdin.readline().strip().split()
n = int(n)
v = int(v)
lines = []
for i in range(0, n):
	lines.append(sys.stdin.readline().strip())
vehicles = []
for (index, vehicle) in enumerate(lines):
	(typ, capacity) = vehicle.split()
	typ = int(typ)
	capacity = int(capacity)
	eff = capacity / typ
	vehicles.append([eff, typ, capacity, index])
ori_list = vehicles.copy()
vehicles.sort()
lorry_cap = 0
count = 0
caps = 0
indices = []
rev_vehicles = vehicles[::-1]
while lorry_cap < v and count < len(rev_vehicles):
	caps += rev_vehicles[count][2]
	lorry_cap += rev_vehicles[count][1]
	indices.append(rev_vehicles[count][3])
	count += 1
if lorry_cap > v:
	caps -= rev_vehicles[count - 1][2]
	lorry_cap -= rev_vehicles[count - 1][1]
	indices.pop(-1)
	for j in range(count, len(rev_vehicles)):
		if rev_vehicles[j][1] == 1:
			caps += rev_vehicles[j][2]
			lorry_cap += rev_vehicles[j][1]
			indices.append(rev_vehicles[j][3])
			break
if lorry_cap < v and count < len(rev_vehicles):
	for l in range(count - 1, len(rev_vehicles)):
		for a in indices[::-1]:
			if ori_list[a][1] == 1 and ori_list[a][2] < rev_vehicles[l][2]:
				caps -= ori_list[a][2]
				caps += rev_vehicles[l][2]
				indices.remove(a)
				indices.append(rev_vehicles[l][3])
				break
		else:
			continue
		break
print(caps)
num_veh = ''
for m in indices:
	num_veh += str(m + 1)
	num_veh += ' '
print(num_veh[:-1])


__author__ = 'Darren'

def solve():
	import sys
	stdin = sys.stdin if True else open('data')
	(n, v) = map(int, next(stdin).split())
	(kayaks, catamarans) = ([], [])
	for i in range(n):
		(t, p) = map(int, next(stdin).split())
		if t == 1:
			kayaks.append((str(i + 1), p))
		else:
			catamarans.append((str(i + 1), p))
	get_capacity = lambda x: x[1]
	kayaks.sort(key=get_capacity, reverse=True)
	catamarans.sort(key=get_capacity, reverse=True)
	(num_kayaks, num_catamarans) = (len(kayaks), len(catamarans))
	last_kayak = min(v, num_kayaks)
	capacity_sum_1 = 0
	for i in range(last_kayak):
		capacity_sum_1 += kayaks[i][1]
	capacity_sum_2 = 0
	max_capacity = capacity_sum_1
	selected_catamarans = 0
	for i in range(1, min(v // 2, num_catamarans) + 1):
		j = min(v - 2 * i, num_kayaks)
		for k in range(j, last_kayak):
			capacity_sum_1 -= kayaks[k][1]
		last_kayak = j
		capacity_sum_2 += catamarans[i - 1][1]
		if capacity_sum_1 + capacity_sum_2 > max_capacity:
			max_capacity = capacity_sum_1 + capacity_sum_2
			selected_catamarans = i
	print(max_capacity)
	result = []
	for i in range(selected_catamarans):
		result.append(catamarans[i][0])
	for i in range(min(v - selected_catamarans * 2, num_kayaks)):
		result.append(kayaks[i][0])
	print(' '.join(result))
solve()


(n, v) = map(int, input().split())
boat_list = []
for _ in range(n):
	(t, p) = map(int, input().split())
	boat_list.append([t, p])
boat1 = []
boat2 = []
for i in range(n):
	if boat_list[i][0] == 1:
		boat1.append([boat_list[i][1], i + 1])
	else:
		boat2.append([boat_list[i][1], i + 1])
boat1 = list(sorted(boat1, key=lambda x: x[0]))
boat2 = list(sorted(boat2, key=lambda x: x[0]))
p1 = len(boat1) - 1
p2 = len(boat2) - 1
cv = v
final_p = 0
while p1 >= 0:
	final_p += boat1[p1][0]
	p1 -= 1
	cv -= 1
	if cv == 0:
		break
if cv > 0:
	while cv - 2 >= 0 and p2 >= 0:
		final_p += boat2[p2][0]
		p2 -= 1
		cv -= 2
while True:
	if p1 <= len(boat1) - 3 and p2 >= 0:
		if boat1[p1 + 1][0] + boat1[p1 + 2][0] < boat2[p2][0]:
			final_p = final_p - boat1[p1 + 1][0] - boat1[p1 + 2][0] + boat2[p2][0]
			p1 += 2
			p2 -= 1
		else:
			break
	else:
		break
if cv == 1:
	if p1 >= 0:
		final_p += boat1[p1][0]
		p1 -= 1
		cv -= 1
	if p2 >= 0 and p1 + 1 < len(boat1) and (cv == 1):
		if boat1[p1 + 1][0] < boat2[p2][0]:
			final_p = final_p - boat1[p1 + 1][0] + boat2[p2][0]
			p2 -= 1
			p1 += 1
			cv -= 1
	elif p2 >= 0 and p1 + 2 < len(boat1) and (cv == 0):
		if boat1[p1 + 1][0] + boat1[p1 + 2][0] < boat2[p2][0]:
			final_p = final_p - boat1[p1 + 1][0] - boat1[p1 + 2][0] + boat2[p2][0]
			p1 += 2
			p2 -= 1
print(final_p)
for b1 in range(p1 + 1, len(boat1)):
	print(str(boat1[b1][1]) + ' ', end='')
for b2 in range(p2 + 1, len(boat2)):
	print(str(boat2[b2][1]) + ' ', end='')


import time
import itertools
KAYAK = 1
CATAMARAN = 2

def get_boats(num_boats):
	(kayaks, catamarans) = (list(), list())
	for boat_num in range(1, num_boats + 1):
		(type_boat, cap) = map(int, input().strip().split(' '))
		if type_boat == KAYAK:
			kayaks.append((cap, boat_num))
		else:
			catamarans.append((cap, boat_num))
	kayaks.sort(reverse=True)
	catamarans.sort(reverse=True)
	return (kayaks, catamarans)

def get_maxes(kayaks, catamarans, dists):
	cap_kayaks = [0] + list(itertools.accumulate([cap for (cap, i) in kayaks]))
	cap_catamarans = [0] + list(itertools.accumulate([cap for (cap, i) in catamarans]))
	(max_capacity, max_x_y) = (-1, None)
	for (x, y) in dists:
		capacity = cap_kayaks[x] + cap_catamarans[y]
		if capacity > max_capacity:
			max_capacity = capacity
			max_x_y = (x, y)
	print(max_capacity)
	(x, y) = max_x_y
	max_boats = [i for (cap, i) in kayaks[0:x]] + [i for (cap, i) in catamarans[0:y]]
	print(''.join((str(cap) + ' ' for cap in max_boats)))
(num_boats, mx_vol) = map(int, input().strip().split(' '))
(kayaks, catamarans) = get_boats(num_boats)
get_maxes(kayaks, catamarans, [(x, min(len(catamarans), mx_vol - x >> 1)) for x in range(0, min(len(kayaks), mx_vol) + 1)])


from operator import itemgetter
(n, v) = map(int, input().split(' '))
vehicles = {1: [], 2: []}
for i in range(n):
	(vtype, vcarry) = map(int, input().split(' '))
	vehicles[vtype].append((str(i + 1), vcarry))
vehicles[1] = sorted(vehicles[1], key=itemgetter(1), reverse=True)
vehicles[2] = sorted(vehicles[2], key=itemgetter(1), reverse=True)
(i1, i2) = (0, 0)
(s1, s2) = (len(vehicles[1]), len(vehicles[2]))
ans_max = 0
ans_str = []
while v != 0 and (i1 != s1 or i2 != s2):
	if v == 1 or i2 == s2:
		if i1 != s1:
			ans_max += vehicles[1][i1][1]
			ans_str.append(vehicles[1][i1][0])
			v -= 1
			i1 += 1
			continue
		break
	if i1 == s1:
		ans_max += vehicles[2][i2][1]
		ans_str.append(vehicles[2][i2][0])
		v -= 2
		i2 += 1
		continue
	if vehicles[1][i1][1] >= vehicles[2][i2][1] or (i1 != s1 - 1 and vehicles[1][i1][1] + vehicles[1][i1 + 1][1] >= vehicles[2][i2][1]):
		ans_max += vehicles[1][i1][1]
		ans_str.append(vehicles[1][i1][0])
		v -= 1
		i1 += 1
	else:
		ans_max += vehicles[2][i2][1]
		ans_str.append(vehicles[2][i2][0])
		v -= 2
		i2 += 1
print(ans_max)
print(*ans_str, sep=' ')


import sys
line = list(map(int, sys.stdin.readline().split()))
n = line[0]
v = line[1]
kayaks = []
catamarans = []
for i in range(0, n):
	nums = list(map(int, sys.stdin.readline().split()))
	if nums[0] == 1:
		kayaks.append((nums[1], i + 1))
	else:
		catamarans.append((nums[1], i + 1))
kayaks.sort(key=lambda pair: pair[0])
catamarans.sort(key=lambda pair: pair[0])
truck = []
while v > 0:
	if v == 1:
		if kayaks:
			truck.append(kayaks.pop())
		v -= 1
	elif not kayaks and (not catamarans):
		v = 0
	elif not kayaks:
		truck.append(catamarans.pop())
		v -= 2
	elif not catamarans:
		truck.append(kayaks.pop())
		v -= 1
	elif len(kayaks) == 1:
		if kayaks[0][0] > catamarans[-1][0]:
			truck.append(kayaks.pop())
			v -= 1
		else:
			truck.append(catamarans.pop())
			v -= 2
	elif kayaks[-1][0] + kayaks[-2][0] > catamarans[-1][0]:
		truck.append(kayaks.pop())
		v -= 1
	else:
		truck.append(catamarans.pop())
		v -= 2
s = 0
for pair in truck:
	s += pair[0]
print(s)
for pair in truck:
	sys.stdout.write(str(pair[1]) + ' ')


(n, v) = tuple(map(int, input().split()))
vehicles = []
vehicles1 = []
res1 = []
res2 = []
res = []
for i in range(n):
	lst = input().split()
	vehicles.append((int(lst[1]), int(lst[0]), i))
	if lst[0] == '1':
		vehicles1.append((int(lst[1]), int(lst[0]), i))
vehicles.sort(reverse=True)
vehicles1.sort(reverse=True)
sumv = 0
for x in vehicles:
	if sumv + x[1] <= v:
		sumv += x[1]
		if x[1] == 1:
			res1.append(x)
			vehicles1.remove(x)
		else:
			res2.append(x)
res2.reverse()
for x in res2:
	if len(vehicles1) > 1 and x[0] < vehicles1[0][0] + vehicles1[1][0]:
		res.append(vehicles1[0])
		res.append(vehicles1[1])
		vehicles1.remove(vehicles1[0])
		vehicles1.remove(vehicles1[0])
	else:
		res.append(x)
res += res1
total = sum([x[0] for x in res])
numbers = ' '.join([str(x[2] + 1) for x in res])
print(total)
print(numbers)


from pprint import pprint
(n, limit) = [int(s) for s in input().split()]
kayaks = []
catamarans = []
for i in range(1, n + 1):
	(type, capacity) = [int(s) for s in input().split()]
	if type == 1:
		kayaks.append((capacity, i))
	else:
		catamarans.append((capacity, i))
result_capacity = 0
result_boats = []
kayaks.sort(reverse=True, key=lambda elem: elem[0])
k_i = 0
catamarans.sort(reverse=True, key=lambda elem: elem[0])
c_i = 0
if len(kayaks) + 2 * len(catamarans) <= limit:
	result_capacity = sum((k[0] for k in kayaks)) + sum((c[0] for c in catamarans))
	result_boats = range(1, n + 1)
else:
	if limit % 2 != 0 and k_i < len(kayaks) and (k_i + 2 * c_i + 1 < limit):
		result_capacity += kayaks[k_i][0]
		result_boats.append(kayaks[k_i][1])
		k_i += 1
	while k_i + 1 < len(kayaks) and c_i < len(catamarans) and (k_i + 2 * c_i + 1 < limit):
		k_capacity = kayaks[k_i][0] + kayaks[k_i + 1][0]
		c_capacity = catamarans[c_i][0]
		if k_capacity < c_capacity:
			result_capacity += c_capacity
			result_boats.append(catamarans[c_i][1])
			c_i += 1
		else:
			result_capacity += k_capacity
			result_boats.append(kayaks[k_i][1])
			result_boats.append(kayaks[k_i + 1][1])
			k_i += 2
	while k_i == len(kayaks) - 1 and c_i < len(catamarans) and (k_i + 2 * c_i + 1 < limit):
		if kayaks[k_i][0] < catamarans[c_i][0]:
			result_capacity += catamarans[c_i][0]
			result_boats.append(catamarans[c_i][1])
			c_i += 1
		else:
			result_capacity += kayaks[k_i][0]
			result_boats.append(kayaks[k_i][1])
			k_i += 1
	while c_i < len(catamarans) and k_i + 2 * c_i + 1 < limit:
		result_capacity += catamarans[c_i][0]
		result_boats.append(catamarans[c_i][1])
		c_i += 1
	while k_i < len(kayaks) and k_i + 2 * c_i < limit:
		result_capacity += kayaks[k_i][0]
		result_boats.append(kayaks[k_i][1])
		k_i += 1
print(result_capacity)
print(' '.join([str(n) for n in result_boats]))


(n, v) = tuple(map(int, input().split()))
boats = []
for i in range(n):
	(t, c) = tuple(map(int, input().split()))
	d = c / t
	if t == 1:
		d += 1e-07
	boats.append((d, t, c, i + 1))
boats.sort(key=lambda tpl: tpl[0], reverse=True)
sumt = 0
sumc = 0
boatorder = []
last1 = None
last1_idx = None
for i in range(n):
	(d, t, c, n) = boats[i]
	if sumt + t <= v:
		boatorder.append(n)
		sumc += c
		sumt += t
		if t == 1:
			last1 = (d, t, c, n)
			last1_idx = len(boatorder) - 1
	elif last1 != None:
		(l1d, l1t, l1c, l1n) = last1
		if sumc - l1c + c > sumc:
			del boatorder[last1_idx]
			boatorder.append(n)
			sumc = sumc - l1c + c
			sumt = sumt - l1t + t
	if sumt == v:
		break
print(sumc)
print(' '.join(map(str, boatorder)))


(n, p) = map(int, input().split())
a = [0] * n
for i in range(n):
	(t, v) = map(int, input().split())
	a[i] = (i, t, v)
a.sort(key=lambda x: x[2] / x[1], reverse=True)
(ans, index, lst) = (0, 0, [])
last1 = (-1, 0)
while p > 0 and index < n:
	(i, t, v) = a[index]
	if t == 1:
		last1 = (i, v)
	p -= t
	ans += v
	lst.append(i)
	index += 1
if p == -1:
	now = (i, v)
	while t == 2 and index < n:
		(i, t, v) = a[index]
		index += 1
	if last1[0] > -1 and t == 1:
		if v + last1[1] < now[1]:
			ans -= last1[1]
			lst.remove(last1[0])
		else:
			ans = ans - now[1] + v
			lst.remove(now[0])
			lst.append(i)
	elif last1[0] > -1 and t == 2:
		ans -= last1[1]
		lst.remove(last1[0])
	elif t == 1 and last1[0] == -1:
		ans = ans - now[1] + v
		lst.remove(now[0])
		lst.append(i)
	else:
		ans -= now[1]
		lst.remove(now[0])
print(ans)
for i in lst:
	print(i + 1, end=' ')


import sys
(n, v) = list(map(int, sys.stdin.readline().rstrip().split()))
kc_ls = []
kayaks = []
catamaran = []
total_space = 0
total_capacity = 0
for i in range(1, n + 1):
	kc_ls.append(tuple(map(int, sys.stdin.readline().rstrip().split() + [i])))
kc_ls.sort(key=lambda x: x[1] if x[0] == 1 else x[1] / 2)
while v - total_space > 1 and len(kc_ls) > 0:
	(t, p, num) = kc_ls.pop()
	total_space += t
	total_capacity += p
	if t == 1:
		kayaks.append((t, p, num))
	else:
		catamaran.append((t, p, num))
if len(kc_ls) > 0:
	if v - total_space == 1:
		(tc, pc, numc) = kc_ls.pop()
		if tc == 1:
			kayaks.append((tc, pc, numc))
			total_space += tc
			total_capacity += pc
		elif len(kayaks) > 0:
			(tk, pk, numk) = kayaks[-1]
			tk1 = 2
			while tk1 != 1 and len(kc_ls) > 0:
				(tk1, pk1, numk1) = kc_ls.pop()
			if tk1 == 1:
				if pk + pk1 < pc:
					kayaks.pop()
					catamaran.append((tc, pc, numc))
					total_capacity += pc - pk
					total_space += tc - tk
				else:
					kayaks.append((tk1, pk1, numk1))
					total_space += tk1
					total_capacity += pk1
			elif pk < pc:
				kayaks.pop()
				catamaran.append((tc, pc, numc))
				total_capacity += pc - pk
				total_space += tc - tk
kayaks.extend(catamaran)
print(total_capacity)
if len(kayaks) > 0:
	print(' '.join([str(i[2]) for i in kayaks]))
else:
	print()


from itertools import islice, chain, accumulate
(n, v) = (int(i) for i in input().split(' '))
little = []
big = []
for index in range(n):
	(t, m) = input().split(' ')
	(t, m) = (int(t), int(m))
	(little if t == 1 else big).append((m, index))
little.sort(key=lambda item: -item[0])
little = little[:v]
little_acc = list(accumulate((item[0] for item in little)))
big.sort(key=lambda item: -item[0])
big_acc = list(accumulate((item[0] for item in big)))

def boats_for_replacements(replacements):
	return chain(islice(little, little_cnt(replacements)), islice(big, big_cnt(replacements)))

def big_cnt(replacements):
	return min(max(0, (v - little_cnt(replacements)) // 2), len(big))

def little_cnt(replacements):
	cnt = len(little) - replacements * 2
	if replacements and v % 2 != len(little) % 2:
		cnt += 1
	return max(0, cnt)

def sum_for_replacements(replacements):
	result = 0
	lc = little_cnt(replacements)
	if lc:
		result += little_acc[lc - 1]
	bc = big_cnt(replacements)
	if bc:
		result += big_acc[bc - 1]
	return result

def gen():
	max_replacements = max(len(big) - big_cnt(0), 1)
	best = 0
	for replacements in range(max_replacements + 1):
		result = sum_for_replacements(replacements)
		if result <= best:
			return (best, replacements - 1)
		best = result
	return (best, replacements)
(total, replacements) = gen()
print(total)
print('\n'.join((str(item[1] + 1) for item in boats_for_replacements(replacements))))


(n, v) = map(int, input().split())
l1 = []
l2 = []
for i in range(0, n):
	(t, p) = map(int, input().split())
	if t == 1:
		l1.append((p, i + 1))
	else:
		l2.append((p, i + 1))
l1 = sorted(l1, key=lambda tup: tup[0], reverse=True)
l2 = sorted(l2, key=lambda tup: tup[0], reverse=True)
sum1 = [0]
sum2 = [0]
for i in l1:
	sum1.append(sum1[-1] + i[0])
for i in l2:
	sum2.append(sum2[-1] + i[0])
res = 0
nums = [0, 0]
for n1 in range(0, min(v + 1, len(l1) + 1)):
	n2 = min(len(l2), int((v - n1) / 2))
	temp = sum1[n1] + sum2[n2]
	if temp > res:
		res = temp
		nums = [n1, n2]
l = []
for i in range(0, nums[0]):
	l.append(l1[i][1])
for i in range(0, nums[1]):
	l.append(l2[i][1])
print(res)
for i in l:
	print(i, end=' ')


(n, v) = map(int, input().split())
list1 = []
list2 = []
for i in range(n):
	(t, p) = map(int, input().split())
	if t == 1:
		list1.append([p, i + 1])
	else:
		list2.append([p, i + 1])
list1.sort(reverse=True)
list2.sort(reverse=True)
temp1 = [0]
temp2 = [0]
for i in range(0, min(v, len(list1))):
	temp1.append(temp1[-1] + list1[i][0])
for i in range(min(int(v / 2), len(list2))):
	temp2.append(temp2[-1] + list2[i][0])
ans = 0
num = 0
for i in range(min(v, len(list1)) + 1):
	t = temp1[i] + temp2[min(len(list2), int((v - i) / 2))]
	if ans < t:
		(num, ans) = (i, t)
print(ans)
for i in range(num):
	print(list1[i][1])
for i in range(min(len(list2), int((v - num) / 2))):
	print(list2[i][1])