Easy and hard versions are actually different problems, so read statements of both problems completely and carefully.

Summer vacation has started so Alice and Bob want to play and joy, but... Their mom doesn't think so. She says that they have to read exactly $m$ books before all entertainments. Alice and Bob will read each book together to end this exercise faster.

There are $n$ books in the family library. The $i$-th book is described by three integers: $t_i$ — the amount of time Alice and Bob need to spend to read it, $a_i$ (equals $1$ if Alice likes the $i$-th book and $0$ if not), and $b_i$ (equals $1$ if Bob likes the $i$-th book and $0$ if not).

So they need to choose exactly $m$ books from the given $n$ books in such a way that:  Alice likes at least $k$ books from the chosen set and Bob likes at least $k$ books from the chosen set;  the total reading time of these $m$ books is minimized (they are children and want to play and joy as soon a possible). 

The set they choose is the same for both Alice an Bob (it's shared between them) and they read all books together, so the total reading time is the sum of $t_i$ over all books that are in the chosen set.

Your task is to help them and find any suitable set of books or determine that it is impossible to find such a set.


-----Input-----

The first line of the input contains three integers $n$, $m$ and $k$ ($1 \le k \le m \le n \le 2 \cdot 10^5$).

The next $n$ lines contain descriptions of books, one description per line: the $i$-th line contains three integers $t_i$, $a_i$ and $b_i$ ($1 \le t_i \le 10^4$, $0 \le a_i, b_i \le 1$), where:  $t_i$ — the amount of time required for reading the $i$-th book;  $a_i$ equals $1$ if Alice likes the $i$-th book and $0$ otherwise;  $b_i$ equals $1$ if Bob likes the $i$-th book and $0$ otherwise. 


-----Output-----

If there is no solution, print only one integer -1.

If the solution exists, print $T$ in the first line — the minimum total reading time of the suitable set of books. In the second line print $m$ distinct integers from $1$ to $n$ in any order — indices of books which are in the set you found.

If there are several answers, print any of them.


-----Examples-----
Input
6 3 1
6 0 0
11 1 0
9 0 1
21 1 1
10 1 0
8 0 1

Output
24
6 5 1 
Input
6 3 2
6 0 0
11 1 0
9 0 1
21 1 1
10 1 0
8 0 1

Output
39
4 6 5

Difficulty: MEDIUM

Starter code:

Solutions:
import sys
inp = [int(x) for x in sys.stdin.read().split()]
ii = 0
seg = [0] * 200000

def offset(x):
	return x + 100000

def encode(x, y):
	return x * 200002 + y

def decode(x):
	return (x // 200002, x % 200002)

def upd(node, L, R, pos, val):
	while L < R:
		seg[node] += val
		seg[offset(node)] += val * pos
		if L + 1 == R:
			break
		M = (L + R) // 2
		node <<= 1
		if pos < M:
			R = M
		else:
			L = M
			node += 1

def query(node, L, R, k):
	ret = 0
	while L < R:
		if k == 0:
			return ret
		if seg[node] == k:
			return ret + seg[offset(node)]
		if L + 1 == R:
			return ret + k * L
		M = (L + R) // 2
		node <<= 1
		if seg[node] >= k:
			R = M
		else:
			ret += seg[offset(node)]
			k -= seg[node]
			L = M
			node += 1
	return ret
(n, m, k) = inp[ii:ii + 3]
ii += 3
(A, B, both, neither) = ([], [], [], [])
for i in range(n):
	(t, a, b) = inp[ii:ii + 3]
	ii += 3
	if a == 0 and b == 0:
		neither.append(encode(t, i + 1))
	if a == 1 and b == 0:
		A.append(encode(t, i + 1))
	if a == 0 and b == 1:
		B.append(encode(t, i + 1))
	if a == 1 and b == 1:
		both.append(encode(t, i + 1))
	upd(1, 0, 10001, t, 1)
A.sort()
B.sort()
both.sort()
p1 = min(k, len(both))
p2 = k - p1
if 2 * k - p1 > m or p2 > min(len(A), len(B)):
	print(-1)
	return
(sum, ans, ch) = (0, 2 ** 31, p1)
for i in range(p1):
	sum += both[i] // 200002
	upd(1, 0, 10001, both[i] // 200002, -1)
for i in range(p2):
	sum += A[i] // 200002 + B[i] // 200002
	upd(1, 0, 10001, A[i] // 200002, -1)
	upd(1, 0, 10001, B[i] // 200002, -1)
ans = query(1, 0, 10001, m - 2 * k + p1) + sum
while p1 > 0:
	if p2 == min(len(A), len(B)):
		break
	upd(1, 0, 10001, A[p2] // 200002, -1)
	sum += A[p2] // 200002
	upd(1, 0, 10001, B[p2] // 200002, -1)
	sum += B[p2] // 200002
	upd(1, 0, 10001, both[p1 - 1] // 200002, 1)
	sum -= both[p1 - 1] // 200002
	p2 += 1
	p1 -= 1
	if m - 2 * k + p1 < 0:
		break
	Q = query(1, 0, 10001, m - 2 * k + p1)
	if ans > sum + Q:
		ans = sum + Q
		ch = p1
print(ans)
ind = [both[i] % 200002 for i in range(ch)] + [A[i] % 200002 for i in range(k - ch)] + [B[i] % 200002 for i in range(k - ch)]
st = neither + [both[i] for i in range(ch, len(both))] + [A[i] for i in range(k - ch, len(A))] + [B[i] for i in range(k - ch, len(B))]
st.sort()
ind += [st[i] % 200002 for i in range(m - 2 * k + ch)]
print(' '.join((str(x) for x in ind)))


import sys

def input():
	return sys.stdin.readline().rstrip()

def input_split():
	return [int(i) for i in input().split()]

def add_book():
	global freqs, cf, cp
	while True:
		if cf < freqs[cp]:
			cf += 1
			return cp
		else:
			cp += 1
			cf = 0

def remove_book():
	global freqs, cf, cp
	while True:
		if cf > 0:
			cf -= 1
			return -cp
		else:
			cp -= 1
			cf = freqs[cp]

def make_available(b_time):
	global freqs, cf, cp
	freqs[b_time] += 1
	if b_time < cp:
		return b_time + remove_book()
	else:
		return 0

def make_unavailable(b_time):
	global freqs, cf, cp
	if b_time < cp:
		freqs[b_time] -= 1
		return -b_time + add_book()
	elif b_time == cp and cf == freqs[cp]:
		freqs[b_time] -= 1
		cf -= 1
		return -b_time + add_book()
	else:
		freqs[b_time] -= 1
		return 0
(n, m, k) = input_split()
times = []
alice_likes = []
bob_likes = []
for _ in range(n):
	(t, a, b) = input_split()
	times.append(t)
	alice_likes.append(a)
	bob_likes.append(b)
times_both = []
times_alice = []
times_bob = []
times_none = []
for book in range(n):
	if alice_likes[book] == 1 and bob_likes[book] == 1:
		times_both.append((times[book], book))
	elif alice_likes[book] == 1:
		times_alice.append((times[book], book))
	elif bob_likes[book] == 1:
		times_bob.append((times[book], book))
	else:
		times_none.append((times[book], book))
times_both.sort()
times_alice.sort()
times_bob.sort()
started = False
possibilities = []
for i in range(k + 1):
	both = i
	indi = k - i
	extra = m - (both + 2 * indi)
	if both > len(times_both) or indi > min(len(times_alice), len(times_bob)) or extra < 0:
		continue
	if not started:
		started = True
		ans = sum([i for (i, j) in times_both[:both]])
		ans += sum([i for (i, j) in times_alice[:indi]])
		ans += sum([i for (i, j) in times_bob[:indi]])
		freqs = [0 for i in range(10001)]
		pending = times_both[both:] + times_bob[indi:] + times_alice[indi:] + times_none
		for (tim, _) in pending:
			freqs[tim] += 1
		cp = 0
		cf = 0
		extra_cost = 0
		count = 0
		for _ in range(extra):
			extra_cost += add_book()
		ans += extra_cost
		possibilities.append((ans, both))
	else:
		last_ans = possibilities[-1][0]
		ans = last_ans
		new_book1_time = times_alice[indi][0]
		new_book2_time = times_bob[indi][0]
		old_book_time = times_both[both - 1][0]
		ans += old_book_time
		ans -= new_book1_time
		ans -= new_book2_time
		ans += make_available(new_book1_time)
		ans += make_available(new_book2_time)
		ans += make_unavailable(old_book_time)
		ans += add_book()
		possibilities.append((ans, both))
if len(possibilities) == 0:
	print(-1)
else:
	(ans, both) = min(possibilities)
	indi = k - both
	extra = m - (indi * 2 + both)
	books = []
	books += [j for (i, j) in times_both[:both]]
	books += [j for (i, j) in times_alice[:indi]]
	books += [j for (i, j) in times_bob[:indi]]
	pending = times_both[both:] + times_bob[indi:] + times_alice[indi:] + times_none
	pending.sort()
	books += [j for (i, j) in pending[:extra]]
	books = [b + 1 for b in books]
	print(ans)
	print(*books, sep=' ')


import bisect
import sys
import math
input = sys.stdin.readline
import functools
import heapq
from collections import defaultdict

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def solve():
	[n, m, k] = inlt()
	bks = []
	for i in range(n):
		[t, a, b] = inlt()
		bks.append((t, a, b, i + 1))
	bks.sort(key=lambda x: x[0])
	aa_i = [v for v in bks if v[1] == 1 and v[2] == 0]
	bb_i = [v for v in bks if v[1] == 0 and v[2] == 1]
	cc_i = [v for v in bks if v[1] == 1 and v[2] == 1]
	dd_i = [v for v in bks if v[1] == 0 and v[2] == 0]
	aa = [0]
	bb = [0]
	cc = [0]
	dd = [0]
	for v in bks:
		if v[1] == 1 and v[2] == 0:
			aa.append(aa[-1] + v[0])
		if v[1] == 0 and v[2] == 1:
			bb.append(bb[-1] + v[0])
		if v[1] == 1 and v[2] == 1:
			cc.append(cc[-1] + v[0])
		if v[1] == 0 and v[2] == 0:
			dd.append(dd[-1] + v[0])
	take_a = min(len(aa) - 1, k)
	take_b = min(len(bb) - 1, k)
	take_c = 0
	take_d = 0
	while True:
		if take_c >= len(cc) - 1:
			break
		picked = take_a + take_b + take_c + take_d
		if take_a + take_c < k or take_b + take_c < k:
			take_c += 1
		elif take_a > 0 and take_b > 0 and (picked > m):
			take_c += 1
		elif take_a > 0 and take_b > 0 and (aa[take_a - 1] + bb[take_b - 1] + cc[take_c + 1] < aa[take_a] + bb[take_b] + cc[take_c]):
			take_c += 1
		else:
			break
		while take_a + take_c > k and take_a > 0:
			take_a -= 1
		while take_b + take_c > k and take_b > 0:
			take_b -= 1
	if take_a + take_c < k or take_b + take_c < k or take_a + take_b + take_c + take_d > m:
		print(-1)
		return
	while take_a + take_b + take_c + take_d < m:
		cases = [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1], [1, 1, -1, 0]]
		cases = [[take_a + case[0], take_b + case[1], take_c + case[2], take_d + case[3]] for case in cases]
		flag = False
		for (i, case) in enumerate(cases):
			new_take_a = case[0]
			new_take_b = case[1]
			new_take_c = case[2]
			new_take_d = case[3]
			if new_take_a < 0 or new_take_a >= len(aa):
				continue
			if new_take_b < 0 or new_take_b >= len(bb):
				continue
			if new_take_c < 0 or new_take_c >= len(cc):
				continue
			if new_take_d < 0 or new_take_d >= len(dd):
				continue
			if not flag or aa[new_take_a] + bb[new_take_b] + cc[new_take_c] + dd[new_take_d] < aa[take_a] + bb[take_b] + cc[take_c] + dd[take_d]:
				(take_a, take_b, take_c, take_d) = (new_take_a, new_take_b, new_take_c, new_take_d)
				flag = True
	res = aa[take_a] + bb[take_b] + cc[take_c] + dd[take_d]
	res_arr = []
	for i in range(take_a):
		res_arr.append(aa_i[i][3])
	for i in range(take_b):
		res_arr.append(bb_i[i][3])
	for i in range(take_c):
		res_arr.append(cc_i[i][3])
	for i in range(take_d):
		res_arr.append(dd_i[i][3])
	res_arr.sort()
	res_arr = [str(v) for v in res_arr]
	print(res)
	print(' '.join(res_arr))
	return res
if len(sys.argv) > 1 and sys.argv[1].startswith('input'):
	f = open('./' + sys.argv[1], 'r')
	input = f.readline
res = solve()


def cta(t, p, r):
	global ana, iva, an
	ana[iva[t][p][1]] ^= True
	an += iva[t][p][0] * r
(n, m, k) = [int(x) for x in input().split()]
iva = [[] for _ in range(4)]
alv = [() for _ in range(n)]
for i in range(n):
	(v, o, u) = [int(x) for x in input().split()]
	q = o << 1 | u
	iva[q].append((v, i))
	alv[i] = (v, i)
for e in iva:
	e.sort()
alv.sort()
(ct, a, r, ps, an) = (0, 0, 0, min(len(iva[1]), len(iva[2])), 0)
ana = [False] * n
for _ in range(k):
	if a < ps and r < len(iva[3]):
		if iva[1][a][0] + iva[2][a][0] < iva[3][r][0]:
			cta(1, a, 1)
			cta(2, a, 1)
			ct += 2
			a += 1
		else:
			cta(3, r, 1)
			ct += 1
			r += 1
	elif a < ps:
		cta(1, a, 1)
		cta(2, a, 1)
		ct += 2
		a += 1
	elif r < len(iva[3]):
		cta(3, r, 1)
		ct += 1
		r += 1
	else:
		print(-1)
		exit(0)
while ct > m and a > 0 and (r < len(iva[3])):
	a -= 1
	cta(1, a, -1)
	cta(2, a, -1)
	cta(3, r, 1)
	ct -= 1
	r += 1
ap = 0
while ct < m and ap < n:
	if not ana[alv[ap][1]]:
		if r > 0 and a < ps and (iva[1][a][0] + iva[2][a][0] - iva[3][r - 1][0] < alv[ap][0]):
			if ana[iva[1][a][1]] or ana[iva[2][a][1]]:
				a += 1
				continue
			r -= 1
			cta(1, a, 1)
			cta(2, a, 1)
			cta(3, r, -1)
			a += 1
			ct += 1
		else:
			ct += 1
			an += alv[ap][0]
			ana[alv[ap][1]] = True
			ap += 1
	else:
		ap += 1
if ct != m:
	print(-1)
else:
	print(an)
	for i in range(n):
		if ana[i]:
			print(i + 1, end=' ')


import io
import os

class SortedListWithSum:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._sum = sum(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._mins = [_list[0] for _list in _lists]
		self._list_lens = [len(_list) for _list in _lists]
		self._fen_tree = []
		self._list_sums = [sum(_list) for _list in _lists]
		self._fen_tree_sum = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._fen_tree_sum[:] = self._list_sums
		_fen_tree_sum = self._fen_tree_sum
		for i in range(len(_fen_tree_sum)):
			if i | i + 1 < len(_fen_tree_sum):
				_fen_tree_sum[i | i + 1] += _fen_tree_sum[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_update_sum(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree_sum
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_query_sum(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree_sum
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		_list_sums = self._list_sums
		value = _lists[pos][idx]
		self._len -= 1
		self._sum -= value
		self._fen_update(pos, -1)
		self._fen_update_sum(pos, -value)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		_list_sums[pos] -= value
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _list_sums[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		_list_sums = self._list_sums
		self._len += 1
		self._sum += value
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			self._fen_update_sum(pos, value)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_list_sums[pos] += value
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				back = _list[_load:]
				old_len = _list_lens[pos]
				old_sum = _list_sums[pos]
				new_len_front = _load
				new_len_back = old_len - new_len_front
				new_sum_back = sum(back)
				new_sum_front = old_sum - new_sum_back
				_lists.insert(pos + 1, back)
				_list_lens.insert(pos + 1, new_len_back)
				_list_sums.insert(pos + 1, new_sum_back)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = new_len_front
				_list_sums[pos] = new_sum_front
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			_list_sums.append(value)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

	def query(self, i, j):
		if i == j:
			return 0
		(pos1, idx1) = self._fen_findkth(self._len + i if i < 0 else i)
		(pos2, idx2) = self._fen_findkth(self._len + j if j < 0 else j)
		return sum(self._lists[pos1][idx1:]) + (self._fen_query_sum(pos2) - self._fen_query_sum(pos1 + 1)) + sum(self._lists[pos2][:idx2])

	def sum(self):
		return self._sum

def solve(N, M, K, books):
	A = []
	B = []
	common = []
	padding = SortedListWithSum()
	for (i, (t, a, b)) in enumerate(books):
		if a and b:
			common.append(t)
		elif a:
			A.append(t)
		elif b:
			B.append(t)
		else:
			padding.add(t)
	A.sort()
	B.sort()
	common.sort()
	prefA = [0]
	for t in A:
		prefA.append(prefA[-1] + t)
	prefB = [0]
	for t in B:
		prefB.append(prefB[-1] + t)
	prefC = [0]
	for t in common:
		prefC.append(prefC[-1] + t)
	cMin = max(0, K - len(A), K - len(B), 2 * K - M)
	cMax = min(K, len(common))
	if cMin > cMax:
		return -1
	for i in range(cMin, len(common)):
		padding.add(common[i])
	for i in range(K - cMin, len(A)):
		padding.add(A[i])
	for i in range(K - cMin, len(B)):
		padding.add(B[i])
	best = (float('inf'),)
	for c in range(cMin, cMax + 1):
		assert 0 <= c <= len(common)
		assert 0 <= K - c <= len(A)
		assert 0 <= K - c <= len(B)
		pad = M - c - (K - c) * 2
		assert 0 <= pad <= N
		cost = prefC[c] + prefB[K - c] + prefA[K - c] + padding.query(0, min(pad, len(padding)))
		best = min(best, (cost, c))
		if 0 <= K - c - 1 < len(A):
			x = A[K - c - 1]
			padding.add(x)
		if 0 <= K - c - 1 < len(B):
			x = B[K - c - 1]
			padding.add(x)
		if c < len(common):
			x = common[c]
			padding.remove(x)
	assert best[0] != float('inf')
	needC = best[1]
	needA = K - needC
	needB = K - needC
	needPad = M - needC - needB - needA
	check = 0
	ans = []
	for (i, (t, a, b)) in sorted(enumerate(books), key=lambda ix: ix[1][0]):
		if a and b:
			if needC:
				needC -= 1
				ans.append(str(i + 1))
				check += t
				continue
		if a:
			if needA:
				needA -= 1
				ans.append(str(i + 1))
				check += t
				continue
		if b:
			if needB:
				needB -= 1
				ans.append(str(i + 1))
				check += t
				continue
		if needPad:
			needPad -= 1
			ans.append(str(i + 1))
			check += t
	assert len(ans) == M
	assert check == best[0]
	return str(best[0]) + '\n' + ' '.join((x for x in ans))
if False:
	import random
	random.seed(0)
	N = 2 * 10 ** 2
	for i in range(1000):
		books = [[random.randint(1, 20), random.randint(0, 1), random.randint(0, 1)] for i in range(N)]
		M = min(N, random.randint(1, 100))
		K = min(M, random.randint(1, 100))
		solve(N, M, K, books)
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N, M, K) = [int(x) for x in input().split()]
books = [[int(x) for x in input().split()] for i in range(N)]
ans = solve(N, M, K, books)
print(ans)


import sys
input = sys.stdin.readline
INF = 10 ** 18
(n, m, k) = map(int, input().split())
B = [tuple(map(int, input().split())) for _ in range(n)]
GB = []
AB = []
BB = []
RB = []
for (i, (t, a, b)) in enumerate(B):
	if a and b:
		GB.append((t, i))
	elif a:
		AB.append((t, i))
	elif b:
		BB.append((t, i))
	else:
		RB.append((t, i))
GB.sort()
AB.sort()
BB.sort()
CB = sorted(((t1 + t2, i1, i2) for ((t1, i1), (t2, i2)) in zip(AB, BB)))
N = 1
while N <= 10 ** 4:
	N *= 2
T = [(0, 0)] * (2 * N)

def comb(a, b):
	return (a[0] + b[0], a[1] + b[1])

def add_book(t, inc=1):
	i = t + N
	T[i] = comb(T[i], (t * inc, inc))
	while i > 1:
		i //= 2
		T[i] = comb(T[i * 2], T[i * 2 + 1])

def query(x):
	assert x >= 0
	s = 0
	i = 1
	while x:
		(ts, tc) = T[i]
		if tc < x:
			return INF
		elif tc == x:
			s += ts
			break
		if i >= N:
			s += ts // tc * x
			break
		i *= 2
		if T[i][1] < x:
			s += T[i][0]
			x -= T[i][1]
			i += 1
	return s
for (t, _) in RB:
	add_book(t)
for (t, _) in AB:
	add_book(t)
for (t, _) in BB:
	add_book(t)
gb_i = 0
gb_t = 0
while gb_i < min(len(GB), m):
	gb_t += GB[gb_i][0]
	gb_i += 1
for (t, _) in GB[gb_i:]:
	add_book(t)
cb_i = 0
cb_t = 0
while gb_i + cb_i < k and gb_i + 2 * (cb_i + 1) <= m and (cb_i < len(CB)):
	cb_t += CB[cb_i][0]
	add_book(AB[cb_i][0], -1)
	add_book(BB[cb_i][0], -1)
	cb_i += 1
if gb_i + cb_i < k:
	print(-1)
	sys.exit()
best = (INF, -1, -1)
while True:
	best = min(best, (gb_t + cb_t + query(m - 2 * cb_i - gb_i), gb_i, cb_i))
	if not gb_i:
		break
	gb_i -= 1
	gb_t -= GB[gb_i][0]
	add_book(GB[gb_i][0])
	if gb_i + cb_i < k:
		if cb_i == len(CB):
			break
		cb_t += CB[cb_i][0]
		add_book(AB[cb_i][0], -1)
		add_book(BB[cb_i][0], -1)
		cb_i += 1
		if gb_i + 2 * cb_i > m:
			break
(bs, bi, bj) = best
assert bs != INF
ans = []
comps = 0
for (t, i) in GB[:bi]:
	ans.append(i + 1)
	comps += t
for (t, i1, i2) in CB[:bj]:
	ans.append(i1 + 1)
	ans.append(i2 + 1)
	comps += t
if bi + 2 * bj < m:
	rem = GB[bi:] + AB[bj:] + BB[bj:] + RB
	rem.sort()
	for (t, i) in rem[:m - bi - 2 * bj]:
		ans.append(i + 1)
		comps += t
assert comps == bs
print(bs)
print(*ans)


line = input()
(n, m, k) = [int(i) for i in line.split(' ')]
(books, allL, aliceL, bobL, other) = (list(range(1, n + 1)), [], [], [], [])
ts = [[] for _ in range(n + 1)]
for i in range(n):
	line = input()
	(t, a, b) = [int(j) for j in line.split(' ')]
	ts[i + 1] = [t, a, b]
	if a == 1 and b == 1:
		allL.append(i + 1)
	elif a == 1:
		aliceL.append(i + 1)
	elif b == 1:
		bobL.append(i + 1)
	else:
		other.append(i + 1)
if len(allL) + min(len(aliceL), len(bobL)) < k or (len(allL) < k and 2 * (k - len(allL)) > m - len(allL)):
	print(-1)
	exit()
books.sort(key=lambda x: (ts[x][0], -ts[x][2] * ts[x][1]))
allL.sort(key=lambda x: (ts[x][0], -ts[x][2] * ts[x][1]))
aliceL.sort(key=lambda x: (ts[x][0], -ts[x][2] * ts[x][1]))
bobL.sort(key=lambda x: (ts[x][0], -ts[x][2] * ts[x][1]))
other.sort(key=lambda x: (ts[x][0], -ts[x][2] * ts[x][1]))
x = max(2 * k - m, 0, k - min(len(aliceL), len(bobL)), m - len(aliceL) - len(bobL) - len(other))
(cura, curb, curo, cur) = (max(0, k - x), max(0, k - x), 0, sum((ts[i][0] for i in allL[:x])))
cur += sum((ts[i][0] for i in aliceL[:cura])) + sum((ts[i][0] for i in bobL[:curb]))
while cura + x + curb + curo < m:
	an = ts[aliceL[cura]][0] if cura < len(aliceL) else 9999999999
	bn = ts[bobL[curb]][0] if curb < len(bobL) else 9999999999
	on = ts[other[curo]][0] if curo < len(other) else 9999999999
	cur += min(an, bn, on)
	if an <= bn and an <= on:
		cura += 1
	elif bn <= an and bn <= on:
		curb += 1
	else:
		curo += 1
(res, a, b, o) = (cur, cura, curb, curo)
for i in range(x + 1, len(allL) + 1):
	cur += ts[allL[i - 1]][0]
	if cura > 0:
		cura -= 1
		cur -= ts[aliceL[cura]][0]
	if curb > 0:
		curb -= 1
		cur -= ts[bobL[curb]][0]
	if curo > 0:
		curo -= 1
		cur -= ts[other[curo]][0]
	while cura + i + curb + curo < m:
		an = ts[aliceL[cura]][0] if cura < len(aliceL) else 9999999999
		bn = ts[bobL[curb]][0] if curb < len(bobL) else 9999999999
		on = ts[other[curo]][0] if curo < len(other) else 9999999999
		cur += min(an, bn, on)
		if an <= bn and an <= on:
			cura += 1
		elif bn <= an and bn <= on:
			curb += 1
		else:
			curo += 1
	if res > cur:
		(res, x, a, b, o) = (cur, i, cura, curb, curo)
print(res)
for i in range(x):
	print(allL[i], end=' ')
for i in range(a):
	print(aliceL[i], end=' ')
for i in range(b):
	print(bobL[i], end=' ')
for i in range(o):
	print(other[i], end=' ')


from sys import stdin, stdout
import heapq

def input():
	return stdin.readline().strip()

def ans(both, alice_only, bob_only, neither, M, K):
	both_fc = [b[0] for b in both]
	neither_fc = [b[0] for b in neither]
	alice_only_fc = [a[0] for a in alice_only]
	bob_only_fc = [b[0] for b in bob_only]
	both_prefix = [0]
	for b in both_fc:
		both_prefix += [both_prefix[-1] + b]
	alice_only_prefix = [0]
	for b in alice_only_fc:
		alice_only_prefix += [alice_only_prefix[-1] + b]
	bob_only_prefix = [0]
	for b in bob_only_fc:
		bob_only_prefix += [bob_only_prefix[-1] + b]
	neither_prefix = [0]
	for b in neither_fc:
		neither_prefix += [neither_prefix[-1] + b]
	p = min(len(both), M)
	q = 0
	r = 0
	s = 0
	while p + q < K:
		if q == len(alice_only):
			break
		q += 1
	if p + q < K:
		return None
	while p + r < K:
		if r == len(bob_only):
			break
		r += 1
	if p + r < K:
		return None
	while p + q + r + s < M:
		g = dict()
		if q < len(alice_only):
			g['q'] = alice_only_fc[q]
		if r < len(bob_only):
			g['r'] = bob_only_fc[r]
		if s < len(neither):
			g['s'] = neither_fc[s]
		if len(g.keys()) == 0:
			return None
		to_increment = min(g, key=g.get)
		if to_increment == 'q':
			q += 1
		if to_increment == 'r':
			r += 1
		if to_increment == 's':
			s += 1
	while p + q + r + s > M:
		g = dict()
		if 0 < q and p + q > K:
			g['q'] = alice_only_fc[q - 1]
		if 0 < r and p + r > K:
			g['r'] = bob_only_fc[r - 1]
		if 0 < s:
			g['s'] = neither_fc[s - 1]
		if len(g.keys()) == 0:
			break
		to_decrement = max(g, key=g.get)
		if to_decrement == 'q':
			q -= 1
		if to_decrement == 'r':
			r -= 1
		if to_decrement == 's':
			s -= 1
	if p + q + r + s > M:
		return None
	best_score = both_prefix[p] + alice_only_prefix[q] + bob_only_prefix[r] + neither_prefix[s]
	best_pqrs = (p, q, r, s)
	while p > 0:
		p -= 1
		while p + q < K:
			if q == len(alice_only):
				break
			q += 1
		if p + q < K:
			break
		while p + r < K:
			if r == len(bob_only):
				break
			r += 1
		if p + r < K:
			break
		while p + q + r + s < M:
			g = dict()
			if q < len(alice_only):
				g['q'] = alice_only_fc[q]
			if r < len(bob_only):
				g['r'] = bob_only_fc[r]
			if s < len(neither):
				g['s'] = neither_fc[s]
			if len(g.keys()) == 0:
				break
			to_increment = min(g, key=g.get)
			if to_increment == 'q':
				q += 1
			if to_increment == 'r':
				r += 1
			if to_increment == 's':
				s += 1
		if p + q + r + s < M:
			break
		while p + q + r + s > M:
			g = dict()
			if 0 < q and p + q > K:
				g['q'] = alice_only_fc[q - 1]
			if 0 < r and p + r > K:
				g['r'] = bob_only_fc[r - 1]
			if 0 < s:
				g['s'] = neither_fc[s - 1]
			if len(g.keys()) == 0:
				break
			to_decrement = max(g, key=g.get)
			if to_decrement == 'q':
				q -= 1
			if to_decrement == 'r':
				r -= 1
			if to_decrement == 's':
				s -= 1
		if p + q + r + s > M:
			break
		score = both_prefix[p] + alice_only_prefix[q] + bob_only_prefix[r] + neither_prefix[s]
		if score < best_score:
			best_score = score
			best_pqrs = (p, q, r, s)
	(p, q, r, s) = best_pqrs
	ret_array = []
	for i in range(p):
		ret_array += [both[i][1]]
	for i in range(q):
		ret_array += [alice_only[i][1]]
	for i in range(r):
		ret_array += [bob_only[i][1]]
	for i in range(s):
		ret_array += [neither[i][1]]
	return (best_score, ret_array)
(N, M, K) = input().split(' ')
N = int(N)
K = int(K)
M = int(M)
alice_only = []
bob_only = []
both = []
neither = []
inorder = []
for i in range(1, N + 1):
	(t, a, b) = input().split(' ')
	t = int(t)
	a = int(a)
	b = int(b)
	if a == 0 and b == 0:
		neither += [(t, i)]
	if a == 1 and b == 1:
		both += [(t, i)]
	if a == 1 and b == 0:
		alice_only += [(t, i)]
	if a == 0 and b == 1:
		bob_only += [(t, i)]
	inorder += [t]
alice_only = sorted(alice_only)
bob_only = sorted(bob_only)
both = sorted(both)
neither = sorted(neither)
ret = ans(both, alice_only, bob_only, neither, M, K)
if ret is None:
	print(-1)
else:
	(a, b) = ret
	print(a)
	print(' '.join(map(str, b)))
	check = 0
	for idx in b:
		check += inorder[idx - 1]
	assert a == check


import heapq
from sys import stdin
input = stdin.readline
INF = 2 * 10 ** 9 + 7
MAX = 10 ** 7 + 7
MOD = 10 ** 9 + 7
(n, M, k) = [int(x) for x in input().strip().split()]
(c, a, b, u) = ([], [], [], [])
for ni in range(n):
	(ti, ai, bi) = [int(x) for x in input().strip().split()]
	if ai == 1 and bi == 1:
		c.append((ti, ni + 1))
	elif ai == 1:
		a.append((ti, ni + 1))
	elif bi == 1:
		b.append((ti, ni + 1))
	else:
		u.append((ti, ni + 1))
c.sort(reverse=True)
a.sort(reverse=True)
b.sort(reverse=True)
u.sort(reverse=True)
alen = len(a)
blen = len(b)
clen = len(c)
ulen = len(u)
m = max(0, k - min(alen, blen), 2 * k - M)
ans = 0
alist = []
adlist = []
if m > clen:
	print('-1')
else:
	for mi in range(m):
		(cv, ci) = c.pop()
		ans += cv
		heapq.heappush(alist, (-cv, ci))
	ka = k - m
	kb = k - m
	M -= m
	while ka or kb:
		ca = c[-1][0] if c else INF
		da = 0
		(ap, bp) = (0, 0)
		if ka:
			da += a[-1][0] if a else INF
			ap = 1
		if kb:
			da += b[-1][0] if b else INF
			bp = 1
		if da <= ca and M >= 2:
			ans += da
			if ap:
				ka -= 1
				adlist.append(a[-1] if a else (INF, -1))
				if a:
					a.pop()
				M -= 1
			if bp:
				kb -= 1
				adlist.append(b[-1] if b else (INF, -1))
				if b:
					b.pop()
				M -= 1
		else:
			ans += ca
			heapq.heappush(alist, (-c[-1][0], c[-1][1]) if c else (INF, -1))
			if c:
				c.pop()
			if ap:
				ka -= 1
			if bp:
				kb -= 1
			M -= 1
	if M > len(a) + len(c) + len(b) + len(u) or ans >= INF:
		print('-1')
	else:
		heapq.heapify(c)
		while M > 0:
			if u and u[-1][0] <= min(c[0][0] if c else INF, a[-1][0] if a else INF, b[-1][0] if b else INF):
				(ut, dt) = (0, 0)
				ut += -alist[0][0] if alist else 0
				ut += u[-1][0]
				dt += a[-1][0] if a else INF
				dt += b[-1][0] if b else INF
				if ut < dt:
					upopped = u.pop()
					adlist.append(upopped)
					M -= 1
					ans += upopped[0]
				else:
					alpopped = heapq.heappop(alist) if alist else (-INF, -1)
					heapq.heappush(c, (-alpopped[0], alpopped[1]))
					ans += alpopped[0]
					bpopped = b.pop() if b else (INF, -1)
					apopped = a.pop() if a else (INF, -1)
					adlist.append(bpopped)
					adlist.append(apopped)
					ans += apopped[0]
					ans += bpopped[0]
					M -= 1
			else:
				ct = c[0][0] if c else INF
				(at, bt) = (a[-1][0] if a else INF, b[-1][0] if b else INF)
				abt = min(at, bt)
				if ct < abt:
					cpopped = heapq.heappop(c) if c else (INF, -1)
					heapq.heappush(alist, (-cpopped[0], cpopped[1]))
					ans += cpopped[0]
					M -= 1
				else:
					if at < bt:
						apopped = a.pop() if a else (INF, -1)
						adlist.append(apopped)
						ans += apopped[0]
					else:
						bpopped = b.pop() if b else (INF, -1)
						adlist.append(bpopped)
						ans += bpopped[0]
					M -= 1
			if ans >= INF:
				break
		print(ans if ans < INF else '-1')
		if ans < INF:
			for ai in adlist:
				print(ai[1], end=' ')
			for ai in alist:
				print(ai[1], end=' ')
			print('')


(n, m, k) = input().split(' ')
(n, m, k) = (int(n), int(m), int(k))
A = []
B = []
C = []
D = []
Ainmax = 0
Binmax = 0
Cinmax = 0
Dinmax = 0
for i in range(n):
	entry = input().split(' ')
	if entry[1] == '1' and entry[2] == '1':
		C.append([int(entry[0]), i + 1])
		Cinmax += 1
	elif entry[1] == '1' and entry[2] == '0':
		A.append([int(entry[0]), i + 1])
		Ainmax += 1
	elif entry[1] == '0' and entry[2] == '1':
		B.append([int(entry[0]), i + 1])
		Binmax += 1
	else:
		D.append([int(entry[0]), i + 1])
		Dinmax += 1
A.sort(key=lambda x: x[0])
B.sort(key=lambda x: x[0])
C.sort(key=lambda x: x[0])
D.sort(key=lambda x: x[0])
mi = min(Ainmax, Binmax)
if len(C) + mi < k:
	print(-1)
elif len(C) < k and 2 * k - len(C) > m:
	print(-1)
else:
	time = 0
	Ain = 0
	Bin = 0
	Cin = 0
	Din = 0
	ABinmax = min(mi, m - k)
	for i in range(k):
		if Ain == ABinmax:
			Cin += 1
		elif Cin == Cinmax or A[Ain][0] + B[Bin][0] <= C[Cin][0]:
			Ain += 1
			Bin += 1
		else:
			Cin += 1
	for i in range(m - Ain - Bin - Cin):
		pot = []
		if Ain < Ainmax:
			pot.append([A[Ain][0], 'Ain+=1'])
		if Bin < Binmax:
			pot.append([B[Bin][0], 'Bin+=1'])
		if Cin < Cinmax:
			pot.append([C[Cin][0], 'Cin+=1'])
		if Din < Dinmax:
			pot.append([D[Din][0], 'Din+=1'])
		if Ain < Ainmax and Bin < Binmax and (Cin != 0):
			pot.append([A[Ain][0] + B[Bin][0] - C[Cin - 1][0], 'Ain+=1;Bin+=1;Cin-=1'])
		minpot = 0
		for j in range(len(pot) - 1):
			if pot[minpot][0] > pot[j + 1][0]:
				minpot = j + 1
		exec(pot[minpot][1])
	for i in range(Ain):
		time += A[i][0]
	for i in range(Bin):
		time += B[i][0]
	for i in range(Cin):
		time += C[i][0]
	for i in range(Din):
		time += D[i][0]
	print(time)
	for i in range(Ain):
		print(A[i][1], end=' ')
	for i in range(Bin):
		print(B[i][1], end=' ')
	for i in range(Cin):
		print(C[i][1], end=' ')
	for i in range(Din):
		print(D[i][1], end=' ')


from __future__ import print_function
import sys
import traceback
from bisect import bisect_left, bisect_right, insort
from itertools import chain, repeat, starmap
from math import log
from operator import add, eq, ne, gt, ge, lt, le, iadd
from textwrap import dedent
try:
	from collections.abc import Sequence, MutableSequence
except ImportError:
	from collections import Sequence, MutableSequence
from functools import wraps
from sys import hexversion
if hexversion < 50331648:
	from itertools import imap as map
	from itertools import izip as zip
	try:
		from thread import get_ident
	except ImportError:
		from dummy_thread import get_ident
else:
	from functools import reduce
	try:
		from _thread import get_ident
	except ImportError:
		from _dummy_thread import get_ident

def recursive_repr(fillvalue='...'):

	def decorating_function(user_function):
		repr_running = set()

		@wraps(user_function)
		def wrapper(self):
			key = (id(self), get_ident())
			if key in repr_running:
				return fillvalue
			repr_running.add(key)
			try:
				result = user_function(self)
			finally:
				repr_running.discard(key)
			return result
		return wrapper
	return decorating_function

class SortedList(MutableSequence):
	DEFAULT_LOAD_FACTOR = 1000

	def __init__(self, iterable=None, key=None):
		assert key is None
		self._len = 0
		self._load = self.DEFAULT_LOAD_FACTOR
		self._lists = []
		self._maxes = []
		self._index = []
		self._offset = 0
		if iterable is not None:
			self._update(iterable)

	def __new__(cls, iterable=None, key=None):
		if key is None:
			return object.__new__(cls)
		elif cls is SortedList:
			return object.__new__(SortedKeyList)
		else:
			raise TypeError('inherit SortedKeyList for key argument')

	@property
	def key(self):
		return None

	def _reset(self, load):
		values = reduce(iadd, self._lists, [])
		self._clear()
		self._load = load
		self._update(values)

	def clear(self):
		self._len = 0
		del self._lists[:]
		del self._maxes[:]
		del self._index[:]
		self._offset = 0
	_clear = clear

	def add(self, value):
		_lists = self._lists
		_maxes = self._maxes
		if _maxes:
			pos = bisect_right(_maxes, value)
			if pos == len(_maxes):
				pos -= 1
				_lists[pos].append(value)
				_maxes[pos] = value
			else:
				insort(_lists[pos], value)
			self._expand(pos)
		else:
			_lists.append([value])
			_maxes.append(value)
		self._len += 1

	def _expand(self, pos):
		_load = self._load
		_lists = self._lists
		_index = self._index
		if len(_lists[pos]) > _load << 1:
			_maxes = self._maxes
			_lists_pos = _lists[pos]
			half = _lists_pos[_load:]
			del _lists_pos[_load:]
			_maxes[pos] = _lists_pos[-1]
			_lists.insert(pos + 1, half)
			_maxes.insert(pos + 1, half[-1])
			del _index[:]
		elif _index:
			child = self._offset + pos
			while child:
				_index[child] += 1
				child = child - 1 >> 1
			_index[0] += 1

	def update(self, iterable):
		_lists = self._lists
		_maxes = self._maxes
		values = sorted(iterable)
		if _maxes:
			if len(values) * 4 >= self._len:
				values.extend(chain.from_iterable(_lists))
				values.sort()
				self._clear()
			else:
				_add = self.add
				for val in values:
					_add(val)
				return
		_load = self._load
		_lists.extend((values[pos:pos + _load] for pos in range(0, len(values), _load)))
		_maxes.extend((sublist[-1] for sublist in _lists))
		self._len = len(values)
		del self._index[:]
	_update = update

	def __contains__(self, value):
		_maxes = self._maxes
		if not _maxes:
			return False
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return False
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		return _lists[pos][idx] == value

	def discard(self, value):
		_maxes = self._maxes
		if not _maxes:
			return
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		if _lists[pos][idx] == value:
			self._delete(pos, idx)

	def remove(self, value):
		_maxes = self._maxes
		if not _maxes:
			raise ValueError('{0!r} not in list'.format(value))
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			raise ValueError('{0!r} not in list'.format(value))
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		if _lists[pos][idx] == value:
			self._delete(pos, idx)
		else:
			raise ValueError('{0!r} not in list'.format(value))

	def _delete(self, pos, idx):
		_lists = self._lists
		_maxes = self._maxes
		_index = self._index
		_lists_pos = _lists[pos]
		del _lists_pos[idx]
		self._len -= 1
		len_lists_pos = len(_lists_pos)
		if len_lists_pos > self._load >> 1:
			_maxes[pos] = _lists_pos[-1]
			if _index:
				child = self._offset + pos
				while child > 0:
					_index[child] -= 1
					child = child - 1 >> 1
				_index[0] -= 1
		elif len(_lists) > 1:
			if not pos:
				pos += 1
			prev = pos - 1
			_lists[prev].extend(_lists[pos])
			_maxes[prev] = _lists[prev][-1]
			del _lists[pos]
			del _maxes[pos]
			del _index[:]
			self._expand(prev)
		elif len_lists_pos:
			_maxes[pos] = _lists_pos[-1]
		else:
			del _lists[pos]
			del _maxes[pos]
			del _index[:]

	def _loc(self, pos, idx):
		if not pos:
			return idx
		_index = self._index
		if not _index:
			self._build_index()
		total = 0
		pos += self._offset
		while pos:
			if not pos & 1:
				total += _index[pos - 1]
			pos = pos - 1 >> 1
		return total + idx

	def _pos(self, idx):
		if idx < 0:
			last_len = len(self._lists[-1])
			if -idx <= last_len:
				return (len(self._lists) - 1, last_len + idx)
			idx += self._len
			if idx < 0:
				raise IndexError('list index out of range')
		elif idx >= self._len:
			raise IndexError('list index out of range')
		if idx < len(self._lists[0]):
			return (0, idx)
		_index = self._index
		if not _index:
			self._build_index()
		pos = 0
		child = 1
		len_index = len(_index)
		while child < len_index:
			index_child = _index[child]
			if idx < index_child:
				pos = child
			else:
				idx -= index_child
				pos = child + 1
			child = (pos << 1) + 1
		return (pos - self._offset, idx)

	def _build_index(self):
		row0 = list(map(len, self._lists))
		if len(row0) == 1:
			self._index[:] = row0
			self._offset = 0
			return
		head = iter(row0)
		tail = iter(head)
		row1 = list(starmap(add, zip(head, tail)))
		if len(row0) & 1:
			row1.append(row0[-1])
		if len(row1) == 1:
			self._index[:] = row1 + row0
			self._offset = 1
			return
		size = 2 ** (int(log(len(row1) - 1, 2)) + 1)
		row1.extend(repeat(0, size - len(row1)))
		tree = [row0, row1]
		while len(tree[-1]) > 1:
			head = iter(tree[-1])
			tail = iter(head)
			row = list(starmap(add, zip(head, tail)))
			tree.append(row)
		reduce(iadd, reversed(tree), self._index)
		self._offset = size * 2 - 1

	def __delitem__(self, index):
		if isinstance(index, slice):
			(start, stop, step) = index.indices(self._len)
			if step == 1 and start < stop:
				if start == 0 and stop == self._len:
					return self._clear()
				elif self._len <= 8 * (stop - start):
					values = self._getitem(slice(None, start))
					if stop < self._len:
						values += self._getitem(slice(stop, None))
					self._clear()
					return self._update(values)
			indices = range(start, stop, step)
			if step > 0:
				indices = reversed(indices)
			(_pos, _delete) = (self._pos, self._delete)
			for index in indices:
				(pos, idx) = _pos(index)
				_delete(pos, idx)
		else:
			(pos, idx) = self._pos(index)
			self._delete(pos, idx)

	def __getitem__(self, index):
		_lists = self._lists
		if isinstance(index, slice):
			(start, stop, step) = index.indices(self._len)
			if step == 1 and start < stop:
				if start == 0 and stop == self._len:
					return reduce(iadd, self._lists, [])
				(start_pos, start_idx) = self._pos(start)
				start_list = _lists[start_pos]
				stop_idx = start_idx + stop - start
				if len(start_list) >= stop_idx:
					return start_list[start_idx:stop_idx]
				if stop == self._len:
					stop_pos = len(_lists) - 1
					stop_idx = len(_lists[stop_pos])
				else:
					(stop_pos, stop_idx) = self._pos(stop)
				prefix = _lists[start_pos][start_idx:]
				middle = _lists[start_pos + 1:stop_pos]
				result = reduce(iadd, middle, prefix)
				result += _lists[stop_pos][:stop_idx]
				return result
			if step == -1 and start > stop:
				result = self._getitem(slice(stop + 1, start + 1))
				result.reverse()
				return result
			indices = range(start, stop, step)
			return list((self._getitem(index) for index in indices))
		else:
			if self._len:
				if index == 0:
					return _lists[0][0]
				elif index == -1:
					return _lists[-1][-1]
			else:
				raise IndexError('list index out of range')
			if 0 <= index < len(_lists[0]):
				return _lists[0][index]
			len_last = len(_lists[-1])
			if -len_last < index < 0:
				return _lists[-1][len_last + index]
			(pos, idx) = self._pos(index)
			return _lists[pos][idx]
	_getitem = __getitem__

	def __setitem__(self, index, value):
		message = 'use ``del sl[index]`` and ``sl.add(value)`` instead'
		raise NotImplementedError(message)

	def __iter__(self):
		return chain.from_iterable(self._lists)

	def __reversed__(self):
		return chain.from_iterable(map(reversed, reversed(self._lists)))

	def reverse(self):
		raise NotImplementedError('use ``reversed(sl)`` instead')

	def islice(self, start=None, stop=None, reverse=False):
		_len = self._len
		if not _len:
			return iter(())
		(start, stop, _) = slice(start, stop).indices(self._len)
		if start >= stop:
			return iter(())
		_pos = self._pos
		(min_pos, min_idx) = _pos(start)
		if stop == _len:
			max_pos = len(self._lists) - 1
			max_idx = len(self._lists[-1])
		else:
			(max_pos, max_idx) = _pos(stop)
		return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)

	def _islice(self, min_pos, min_idx, max_pos, max_idx, reverse):
		_lists = self._lists
		if min_pos > max_pos:
			return iter(())
		if min_pos == max_pos:
			if reverse:
				indices = reversed(range(min_idx, max_idx))
				return map(_lists[min_pos].__getitem__, indices)
			indices = range(min_idx, max_idx)
			return map(_lists[min_pos].__getitem__, indices)
		next_pos = min_pos + 1
		if next_pos == max_pos:
			if reverse:
				min_indices = range(min_idx, len(_lists[min_pos]))
				max_indices = range(max_idx)
				return chain(map(_lists[max_pos].__getitem__, reversed(max_indices)), map(_lists[min_pos].__getitem__, reversed(min_indices)))
			min_indices = range(min_idx, len(_lists[min_pos]))
			max_indices = range(max_idx)
			return chain(map(_lists[min_pos].__getitem__, min_indices), map(_lists[max_pos].__getitem__, max_indices))
		if reverse:
			min_indices = range(min_idx, len(_lists[min_pos]))
			sublist_indices = range(next_pos, max_pos)
			sublists = map(_lists.__getitem__, reversed(sublist_indices))
			max_indices = range(max_idx)
			return chain(map(_lists[max_pos].__getitem__, reversed(max_indices)), chain.from_iterable(map(reversed, sublists)), map(_lists[min_pos].__getitem__, reversed(min_indices)))
		min_indices = range(min_idx, len(_lists[min_pos]))
		sublist_indices = range(next_pos, max_pos)
		sublists = map(_lists.__getitem__, sublist_indices)
		max_indices = range(max_idx)
		return chain(map(_lists[min_pos].__getitem__, min_indices), chain.from_iterable(sublists), map(_lists[max_pos].__getitem__, max_indices))

	def irange(self, minimum=None, maximum=None, inclusive=(True, True), reverse=False):
		_maxes = self._maxes
		if not _maxes:
			return iter(())
		_lists = self._lists
		if minimum is None:
			min_pos = 0
			min_idx = 0
		elif inclusive[0]:
			min_pos = bisect_left(_maxes, minimum)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_left(_lists[min_pos], minimum)
		else:
			min_pos = bisect_right(_maxes, minimum)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_right(_lists[min_pos], minimum)
		if maximum is None:
			max_pos = len(_maxes) - 1
			max_idx = len(_lists[max_pos])
		elif inclusive[1]:
			max_pos = bisect_right(_maxes, maximum)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_lists[max_pos])
			else:
				max_idx = bisect_right(_lists[max_pos], maximum)
		else:
			max_pos = bisect_left(_maxes, maximum)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_lists[max_pos])
			else:
				max_idx = bisect_left(_lists[max_pos], maximum)
		return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)

	def __len__(self):
		return self._len

	def bisect_left(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return self._len
		idx = bisect_left(self._lists[pos], value)
		return self._loc(pos, idx)

	def bisect_right(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_right(_maxes, value)
		if pos == len(_maxes):
			return self._len
		idx = bisect_right(self._lists[pos], value)
		return self._loc(pos, idx)
	bisect = bisect_right
	_bisect_right = bisect_right

	def count(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos_left = bisect_left(_maxes, value)
		if pos_left == len(_maxes):
			return 0
		_lists = self._lists
		idx_left = bisect_left(_lists[pos_left], value)
		pos_right = bisect_right(_maxes, value)
		if pos_right == len(_maxes):
			return self._len - self._loc(pos_left, idx_left)
		idx_right = bisect_right(_lists[pos_right], value)
		if pos_left == pos_right:
			return idx_right - idx_left
		right = self._loc(pos_right, idx_right)
		left = self._loc(pos_left, idx_left)
		return right - left

	def copy(self):
		return self.__class__(self)
	__copy__ = copy

	def append(self, value):
		raise NotImplementedError('use ``sl.add(value)`` instead')

	def extend(self, values):
		raise NotImplementedError('use ``sl.update(values)`` instead')

	def insert(self, index, value):
		raise NotImplementedError('use ``sl.add(value)`` instead')

	def pop(self, index=-1):
		if not self._len:
			raise IndexError('pop index out of range')
		_lists = self._lists
		if index == 0:
			val = _lists[0][0]
			self._delete(0, 0)
			return val
		if index == -1:
			pos = len(_lists) - 1
			loc = len(_lists[pos]) - 1
			val = _lists[pos][loc]
			self._delete(pos, loc)
			return val
		if 0 <= index < len(_lists[0]):
			val = _lists[0][index]
			self._delete(0, index)
			return val
		len_last = len(_lists[-1])
		if -len_last < index < 0:
			pos = len(_lists) - 1
			loc = len_last + index
			val = _lists[pos][loc]
			self._delete(pos, loc)
			return val
		(pos, idx) = self._pos(index)
		val = _lists[pos][idx]
		self._delete(pos, idx)
		return val

	def index(self, value, start=None, stop=None):
		_len = self._len
		if not _len:
			raise ValueError('{0!r} is not in list'.format(value))
		if start is None:
			start = 0
		if start < 0:
			start += _len
		if start < 0:
			start = 0
		if stop is None:
			stop = _len
		if stop < 0:
			stop += _len
		if stop > _len:
			stop = _len
		if stop <= start:
			raise ValueError('{0!r} is not in list'.format(value))
		_maxes = self._maxes
		pos_left = bisect_left(_maxes, value)
		if pos_left == len(_maxes):
			raise ValueError('{0!r} is not in list'.format(value))
		_lists = self._lists
		idx_left = bisect_left(_lists[pos_left], value)
		if _lists[pos_left][idx_left] != value:
			raise ValueError('{0!r} is not in list'.format(value))
		stop -= 1
		left = self._loc(pos_left, idx_left)
		if start <= left:
			if left <= stop:
				return left
		else:
			right = self._bisect_right(value) - 1
			if start <= right:
				return start
		raise ValueError('{0!r} is not in list'.format(value))

	def __add__(self, other):
		values = reduce(iadd, self._lists, [])
		values.extend(other)
		return self.__class__(values)
	__radd__ = __add__

	def __iadd__(self, other):
		self._update(other)
		return self

	def __mul__(self, num):
		values = reduce(iadd, self._lists, []) * num
		return self.__class__(values)
	__rmul__ = __mul__

	def __imul__(self, num):
		values = reduce(iadd, self._lists, []) * num
		self._clear()
		self._update(values)
		return self

	def __make_cmp(seq_op, symbol, doc):

		def comparer(self, other):
			if not isinstance(other, Sequence):
				return NotImplemented
			self_len = self._len
			len_other = len(other)
			if self_len != len_other:
				if seq_op is eq:
					return False
				if seq_op is ne:
					return True
			for (alpha, beta) in zip(self, other):
				if alpha != beta:
					return seq_op(alpha, beta)
			return seq_op(self_len, len_other)
		seq_op_name = seq_op.__name__
		comparer.__name__ = '__{0}__'.format(seq_op_name)
		doc_str = 'Return true if and only if sorted list is {0} `other`.\n        ``sl.__{1}__(other)`` <==> ``sl {2} other``\n        Comparisons use lexicographical order as with sequences.\n        Runtime complexity: `O(n)`\n        :param other: `other` sequence\n        :return: true if sorted list is {0} `other`\n        '
		comparer.__doc__ = dedent(doc_str.format(doc, seq_op_name, symbol))
		return comparer
	__eq__ = __make_cmp(eq, '==', 'equal to')
	__ne__ = __make_cmp(ne, '!=', 'not equal to')
	__lt__ = __make_cmp(lt, '<', 'less than')
	__gt__ = __make_cmp(gt, '>', 'greater than')
	__le__ = __make_cmp(le, '<=', 'less than or equal to')
	__ge__ = __make_cmp(ge, '>=', 'greater than or equal to')
	__make_cmp = staticmethod(__make_cmp)

	def __reduce__(self):
		values = reduce(iadd, self._lists, [])
		return (type(self), (values,))

	@recursive_repr()
	def __repr__(self):
		return '{0}({1!r})'.format(type(self).__name__, list(self))

	def _check(self):
		try:
			assert self._load >= 4
			assert len(self._maxes) == len(self._lists)
			assert self._len == sum((len(sublist) for sublist in self._lists))
			for sublist in self._lists:
				for pos in range(1, len(sublist)):
					assert sublist[pos - 1] <= sublist[pos]
			for pos in range(1, len(self._lists)):
				assert self._lists[pos - 1][-1] <= self._lists[pos][0]
			for pos in range(len(self._maxes)):
				assert self._maxes[pos] == self._lists[pos][-1]
			double = self._load << 1
			assert all((len(sublist) <= double for sublist in self._lists))
			half = self._load >> 1
			for pos in range(0, len(self._lists) - 1):
				assert len(self._lists[pos]) >= half
			if self._index:
				assert self._len == self._index[0]
				assert len(self._index) == self._offset + len(self._lists)
				for pos in range(len(self._lists)):
					leaf = self._index[self._offset + pos]
					assert leaf == len(self._lists[pos])
				for pos in range(self._offset):
					child = (pos << 1) + 1
					if child >= len(self._index):
						assert self._index[pos] == 0
					elif child + 1 == len(self._index):
						assert self._index[pos] == self._index[child]
					else:
						child_sum = self._index[child] + self._index[child + 1]
						assert child_sum == self._index[pos]
		except:
			traceback.print_exc(file=sys.stdout)
			print('len', self._len)
			print('load', self._load)
			print('offset', self._offset)
			print('len_index', len(self._index))
			print('index', self._index)
			print('len_maxes', len(self._maxes))
			print('maxes', self._maxes)
			print('len_lists', len(self._lists))
			print('lists', self._lists)
			raise

def identity(value):
	return value

class SortedKeyList(SortedList):

	def __init__(self, iterable=None, key=identity):
		self._key = key
		self._len = 0
		self._load = self.DEFAULT_LOAD_FACTOR
		self._lists = []
		self._keys = []
		self._maxes = []
		self._index = []
		self._offset = 0
		if iterable is not None:
			self._update(iterable)

	def __new__(cls, iterable=None, key=identity):
		return object.__new__(cls)

	@property
	def key(self):
		return self._key

	def clear(self):
		self._len = 0
		del self._lists[:]
		del self._keys[:]
		del self._maxes[:]
		del self._index[:]
	_clear = clear

	def add(self, value):
		_lists = self._lists
		_keys = self._keys
		_maxes = self._maxes
		key = self._key(value)
		if _maxes:
			pos = bisect_right(_maxes, key)
			if pos == len(_maxes):
				pos -= 1
				_lists[pos].append(value)
				_keys[pos].append(key)
				_maxes[pos] = key
			else:
				idx = bisect_right(_keys[pos], key)
				_lists[pos].insert(idx, value)
				_keys[pos].insert(idx, key)
			self._expand(pos)
		else:
			_lists.append([value])
			_keys.append([key])
			_maxes.append(key)
		self._len += 1

	def _expand(self, pos):
		_lists = self._lists
		_keys = self._keys
		_index = self._index
		if len(_keys[pos]) > self._load << 1:
			_maxes = self._maxes
			_load = self._load
			_lists_pos = _lists[pos]
			_keys_pos = _keys[pos]
			half = _lists_pos[_load:]
			half_keys = _keys_pos[_load:]
			del _lists_pos[_load:]
			del _keys_pos[_load:]
			_maxes[pos] = _keys_pos[-1]
			_lists.insert(pos + 1, half)
			_keys.insert(pos + 1, half_keys)
			_maxes.insert(pos + 1, half_keys[-1])
			del _index[:]
		elif _index:
			child = self._offset + pos
			while child:
				_index[child] += 1
				child = child - 1 >> 1
			_index[0] += 1

	def update(self, iterable):
		_lists = self._lists
		_keys = self._keys
		_maxes = self._maxes
		values = sorted(iterable, key=self._key)
		if _maxes:
			if len(values) * 4 >= self._len:
				values.extend(chain.from_iterable(_lists))
				values.sort(key=self._key)
				self._clear()
			else:
				_add = self.add
				for val in values:
					_add(val)
				return
		_load = self._load
		_lists.extend((values[pos:pos + _load] for pos in range(0, len(values), _load)))
		_keys.extend((list(map(self._key, _list)) for _list in _lists))
		_maxes.extend((sublist[-1] for sublist in _keys))
		self._len = len(values)
		del self._index[:]
	_update = update

	def __contains__(self, value):
		_maxes = self._maxes
		if not _maxes:
			return False
		key = self._key(value)
		pos = bisect_left(_maxes, key)
		if pos == len(_maxes):
			return False
		_lists = self._lists
		_keys = self._keys
		idx = bisect_left(_keys[pos], key)
		len_keys = len(_keys)
		len_sublist = len(_keys[pos])
		while True:
			if _keys[pos][idx] != key:
				return False
			if _lists[pos][idx] == value:
				return True
			idx += 1
			if idx == len_sublist:
				pos += 1
				if pos == len_keys:
					return False
				len_sublist = len(_keys[pos])
				idx = 0

	def discard(self, value):
		_maxes = self._maxes
		if not _maxes:
			return
		key = self._key(value)
		pos = bisect_left(_maxes, key)
		if pos == len(_maxes):
			return
		_lists = self._lists
		_keys = self._keys
		idx = bisect_left(_keys[pos], key)
		len_keys = len(_keys)
		len_sublist = len(_keys[pos])
		while True:
			if _keys[pos][idx] != key:
				return
			if _lists[pos][idx] == value:
				self._delete(pos, idx)
				return
			idx += 1
			if idx == len_sublist:
				pos += 1
				if pos == len_keys:
					return
				len_sublist = len(_keys[pos])
				idx = 0

	def remove(self, value):
		_maxes = self._maxes
		if not _maxes:
			raise ValueError('{0!r} not in list'.format(value))
		key = self._key(value)
		pos = bisect_left(_maxes, key)
		if pos == len(_maxes):
			raise ValueError('{0!r} not in list'.format(value))
		_lists = self._lists
		_keys = self._keys
		idx = bisect_left(_keys[pos], key)
		len_keys = len(_keys)
		len_sublist = len(_keys[pos])
		while True:
			if _keys[pos][idx] != key:
				raise ValueError('{0!r} not in list'.format(value))
			if _lists[pos][idx] == value:
				self._delete(pos, idx)
				return
			idx += 1
			if idx == len_sublist:
				pos += 1
				if pos == len_keys:
					raise ValueError('{0!r} not in list'.format(value))
				len_sublist = len(_keys[pos])
				idx = 0

	def _delete(self, pos, idx):
		_lists = self._lists
		_keys = self._keys
		_maxes = self._maxes
		_index = self._index
		keys_pos = _keys[pos]
		lists_pos = _lists[pos]
		del keys_pos[idx]
		del lists_pos[idx]
		self._len -= 1
		len_keys_pos = len(keys_pos)
		if len_keys_pos > self._load >> 1:
			_maxes[pos] = keys_pos[-1]
			if _index:
				child = self._offset + pos
				while child > 0:
					_index[child] -= 1
					child = child - 1 >> 1
				_index[0] -= 1
		elif len(_keys) > 1:
			if not pos:
				pos += 1
			prev = pos - 1
			_keys[prev].extend(_keys[pos])
			_lists[prev].extend(_lists[pos])
			_maxes[prev] = _keys[prev][-1]
			del _lists[pos]
			del _keys[pos]
			del _maxes[pos]
			del _index[:]
			self._expand(prev)
		elif len_keys_pos:
			_maxes[pos] = keys_pos[-1]
		else:
			del _lists[pos]
			del _keys[pos]
			del _maxes[pos]
			del _index[:]

	def irange(self, minimum=None, maximum=None, inclusive=(True, True), reverse=False):
		min_key = self._key(minimum) if minimum is not None else None
		max_key = self._key(maximum) if maximum is not None else None
		return self._irange_key(min_key=min_key, max_key=max_key, inclusive=inclusive, reverse=reverse)

	def irange_key(self, min_key=None, max_key=None, inclusive=(True, True), reverse=False):
		_maxes = self._maxes
		if not _maxes:
			return iter(())
		_keys = self._keys
		if min_key is None:
			min_pos = 0
			min_idx = 0
		elif inclusive[0]:
			min_pos = bisect_left(_maxes, min_key)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_left(_keys[min_pos], min_key)
		else:
			min_pos = bisect_right(_maxes, min_key)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_right(_keys[min_pos], min_key)
		if max_key is None:
			max_pos = len(_maxes) - 1
			max_idx = len(_keys[max_pos])
		elif inclusive[1]:
			max_pos = bisect_right(_maxes, max_key)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_keys[max_pos])
			else:
				max_idx = bisect_right(_keys[max_pos], max_key)
		else:
			max_pos = bisect_left(_maxes, max_key)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_keys[max_pos])
			else:
				max_idx = bisect_left(_keys[max_pos], max_key)
		return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)
	_irange_key = irange_key

	def bisect_left(self, value):
		return self._bisect_key_left(self._key(value))

	def bisect_right(self, value):
		return self._bisect_key_right(self._key(value))
	bisect = bisect_right

	def bisect_key_left(self, key):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_left(_maxes, key)
		if pos == len(_maxes):
			return self._len
		idx = bisect_left(self._keys[pos], key)
		return self._loc(pos, idx)
	_bisect_key_left = bisect_key_left

	def bisect_key_right(self, key):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_right(_maxes, key)
		if pos == len(_maxes):
			return self._len
		idx = bisect_right(self._keys[pos], key)
		return self._loc(pos, idx)
	bisect_key = bisect_key_right
	_bisect_key_right = bisect_key_right

	def count(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		key = self._key(value)
		pos = bisect_left(_maxes, key)
		if pos == len(_maxes):
			return 0
		_lists = self._lists
		_keys = self._keys
		idx = bisect_left(_keys[pos], key)
		total = 0
		len_keys = len(_keys)
		len_sublist = len(_keys[pos])
		while True:
			if _keys[pos][idx] != key:
				return total
			if _lists[pos][idx] == value:
				total += 1
			idx += 1
			if idx == len_sublist:
				pos += 1
				if pos == len_keys:
					return total
				len_sublist = len(_keys[pos])
				idx = 0

	def copy(self):
		return self.__class__(self, key=self._key)
	__copy__ = copy

	def index(self, value, start=None, stop=None):
		_len = self._len
		if not _len:
			raise ValueError('{0!r} is not in list'.format(value))
		if start is None:
			start = 0
		if start < 0:
			start += _len
		if start < 0:
			start = 0
		if stop is None:
			stop = _len
		if stop < 0:
			stop += _len
		if stop > _len:
			stop = _len
		if stop <= start:
			raise ValueError('{0!r} is not in list'.format(value))
		_maxes = self._maxes
		key = self._key(value)
		pos = bisect_left(_maxes, key)
		if pos == len(_maxes):
			raise ValueError('{0!r} is not in list'.format(value))
		stop -= 1
		_lists = self._lists
		_keys = self._keys
		idx = bisect_left(_keys[pos], key)
		len_keys = len(_keys)
		len_sublist = len(_keys[pos])
		while True:
			if _keys[pos][idx] != key:
				raise ValueError('{0!r} is not in list'.format(value))
			if _lists[pos][idx] == value:
				loc = self._loc(pos, idx)
				if start <= loc <= stop:
					return loc
				elif loc > stop:
					break
			idx += 1
			if idx == len_sublist:
				pos += 1
				if pos == len_keys:
					raise ValueError('{0!r} is not in list'.format(value))
				len_sublist = len(_keys[pos])
				idx = 0
		raise ValueError('{0!r} is not in list'.format(value))

	def __add__(self, other):
		values = reduce(iadd, self._lists, [])
		values.extend(other)
		return self.__class__(values, key=self._key)
	__radd__ = __add__

	def __mul__(self, num):
		values = reduce(iadd, self._lists, []) * num
		return self.__class__(values, key=self._key)

	def __reduce__(self):
		values = reduce(iadd, self._lists, [])
		return (type(self), (values, self.key))

	@recursive_repr()
	def __repr__(self):
		type_name = type(self).__name__
		return '{0}({1!r}, key={2!r})'.format(type_name, list(self), self._key)

	def _check(self):
		try:
			assert self._load >= 4
			assert len(self._maxes) == len(self._lists) == len(self._keys)
			assert self._len == sum((len(sublist) for sublist in self._lists))
			for sublist in self._keys:
				for pos in range(1, len(sublist)):
					assert sublist[pos - 1] <= sublist[pos]
			for pos in range(1, len(self._keys)):
				assert self._keys[pos - 1][-1] <= self._keys[pos][0]
			for (val_sublist, key_sublist) in zip(self._lists, self._keys):
				assert len(val_sublist) == len(key_sublist)
				for (val, key) in zip(val_sublist, key_sublist):
					assert self._key(val) == key
			for pos in range(len(self._maxes)):
				assert self._maxes[pos] == self._keys[pos][-1]
			double = self._load << 1
			assert all((len(sublist) <= double for sublist in self._lists))
			half = self._load >> 1
			for pos in range(0, len(self._lists) - 1):
				assert len(self._lists[pos]) >= half
			if self._index:
				assert self._len == self._index[0]
				assert len(self._index) == self._offset + len(self._lists)
				for pos in range(len(self._lists)):
					leaf = self._index[self._offset + pos]
					assert leaf == len(self._lists[pos])
				for pos in range(self._offset):
					child = (pos << 1) + 1
					if child >= len(self._index):
						assert self._index[pos] == 0
					elif child + 1 == len(self._index):
						assert self._index[pos] == self._index[child]
					else:
						child_sum = self._index[child] + self._index[child + 1]
						assert child_sum == self._index[pos]
		except:
			traceback.print_exc(file=sys.stdout)
			print('len', self._len)
			print('load', self._load)
			print('offset', self._offset)
			print('len_index', len(self._index))
			print('index', self._index)
			print('len_maxes', len(self._maxes))
			print('maxes', self._maxes)
			print('len_keys', len(self._keys))
			print('keys', self._keys)
			print('len_lists', len(self._lists))
			print('lists', self._lists)
			raise
SortedListWithKey = SortedKeyList
import io
import os

def solve(N, M, K, books):
	A = []
	B = []
	common = []
	padding = SortedList()
	paddingSum = 0
	extras = SortedList()
	for (i, (t, a, b)) in enumerate(books):
		if a and b:
			common.append(t)
		elif a:
			A.append(t)
		elif b:
			B.append(t)
		else:
			extras.add(t)
	A.sort()
	B.sort()
	common.sort()
	prefA = [0]
	for t in A:
		prefA.append(prefA[-1] + t)
	prefB = [0]
	for t in B:
		prefB.append(prefB[-1] + t)
	prefC = [0]
	for t in common:
		prefC.append(prefC[-1] + t)
	cMin = max(0, K - len(A), K - len(B), 2 * K - M)
	cMax = min(K, len(common))
	if cMin > cMax:
		return -1
	for i in range(cMin, len(common)):
		extras.add(common[i])
	for i in range(K - cMin, len(A)):
		extras.add(A[i])
	for i in range(K - cMin, len(B)):
		extras.add(B[i])
	best = (float('inf'),)
	for c in range(cMin, cMax + 1):
		assert 0 <= c <= len(common)
		assert 0 <= K - c <= len(A)
		assert 0 <= K - c <= len(B)
		pad = M - c - (K - c) * 2
		assert pad >= 0
		while len(padding) < pad and extras:
			x = extras[0]
			extras.remove(x)
			padding.add(x)
			paddingSum += x
		while len(padding) > pad:
			x = padding[-1]
			padding.remove(x)
			paddingSum -= x
			extras.add(x)
		if len(padding) == pad:
			cost = prefC[c] + prefB[K - c] + prefA[K - c] + paddingSum
			best = min(best, (cost, c))
		assert c + (K - c) + (K - c) + len(padding) + len(extras) == N
		if padding and extras:
			assert padding[-1] <= extras[0]
		if 0 <= K - c - 1 < len(A):
			x = A[K - c - 1]
			if padding and x <= padding[-1]:
				padding.add(x)
				paddingSum += x
			else:
				extras.add(x)
		if 0 <= K - c - 1 < len(B):
			x = B[K - c - 1]
			if padding and x <= padding[-1]:
				padding.add(x)
				paddingSum += x
			else:
				extras.add(x)
		if c < len(common):
			x = common[c]
			if x in extras:
				extras.remove(x)
			elif x in padding:
				padding.remove(x)
				paddingSum -= x
	if best[0] == float('inf'):
		return -1
	needC = best[1]
	needA = K - needC
	needB = K - needC
	needPad = M - needC - needB - needA
	check = 0
	ans = []
	for (i, (t, a, b)) in sorted(enumerate(books), key=lambda ix: ix[1][0]):
		if a and b:
			if needC:
				needC -= 1
				ans.append(str(i + 1))
				check += t
				continue
		if a:
			if needA:
				needA -= 1
				ans.append(str(i + 1))
				check += t
				continue
		if b:
			if needB:
				needB -= 1
				ans.append(str(i + 1))
				check += t
				continue
		if needPad:
			needPad -= 1
			ans.append(str(i + 1))
			check += t
	assert len(ans) == M
	assert check == best[0]
	return str(best[0]) + '\n' + ' '.join((x for x in ans))
if False:
	import random
	random.seed(0)
	N = 2 * 10 ** 5
	for i in range(1):
		books = [[random.randint(1, 20), random.randint(0, 1), random.randint(0, 1)] for i in range(N)]
		solve(len(books), random.randint(1, 100), random.randint(1, 100), books)
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N, M, K) = [int(x) for x in input().split()]
books = [[int(x) for x in input().split()] for i in range(N)]
ans = solve(N, M, K, books)
print(ans)


(n, m, k) = map(int, input().split())
ab = []
a = []
b = []
other = []
l = [list(map(int, input().split())) for i in range(n)]
for i in range(n):
	(t, c, d) = l[i]
	if c and d == 0:
		a.append([t, i + 1])
	elif d and c == 0:
		b.append([t, i + 1])
	elif c * d:
		ab.append([t, i + 1])
	else:
		other.append([t, i + 1])
a.sort()
b.sort()
ab.sort()
other.sort()
la = len(a)
lb = len(b)
lab = len(ab)
lo = len(other)
a.append([float('INF'), -1])
b.append([float('INF'), -1])
ab.append([float('INF'), -1])
other.append([float('INF'), -1])
if la < lb:
	(la, lb) = (lb, la)
	(a, b) = (b, a)
ans = float('INF')
count = 0
ia = 0
ib = 0
iab = 0
io = 0
ana = 0
anb = 0
anab = 0
ano = 0
for i in range(lab + 1):
	if k - i > lb:
		continue
	if 2 * k - i > m:
		continue
	if i + la + lb + lo < m:
		continue
	if ia > 0:
		ia -= 1
		count -= a[ia][0]
	if ib > 0:
		ib -= 1
		count -= b[ib][0]
	if io > 0:
		io -= 1
		count -= other[io][0]
	while ia < la and ia < k - i:
		count += a[ia][0]
		ia += 1
	while ib < lb and ib < k - i:
		count += b[ib][0]
		ib += 1
	while iab < lab and iab < i:
		count += ab[iab][0]
		iab += 1
	while ia + ib + iab + io < m:
		na = a[ia][0]
		nb = b[ib][0]
		no = other[io][0]
		mi = min(na, nb, no)
		if mi == na:
			count += na
			ia += 1
		elif mi == nb:
			count += nb
			ib += 1
		else:
			count += no
			io += 1
	if count < ans:
		ans = count
		ana = ia
		anb = ib
		anab = iab
		ano = io
if ans == float('INF'):
	print(-1)
else:
	print(ans)
	l = []
	for i in range(ana):
		l.append(a[i][1])
	for i in range(anb):
		l.append(b[i][1])
	for i in range(anab):
		l.append(ab[i][1])
	for i in range(ano):
		l.append(other[i][1])
	print(*l)