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 some amount of 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 some 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 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 two integers $n$ and $k$ ($1 \le k \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. Otherwise print one integer $T$ — the minimum total reading time of the suitable set of books.


-----Examples-----
Input
8 4
7 1 1
2 1 1
4 0 1
8 1 1
1 0 1
1 1 1
1 0 1
3 0 0

Output
18

Input
5 2
6 0 0
9 0 0
1 0 1
2 1 1
5 1 0

Output
8

Input
5 3
3 0 0
2 1 0
3 1 0
5 0 1
3 0 1

Output
-1

Difficulty: introductory

Starter code:

Solutions:
from sys import stdin

n,k = list(map(int, stdin.readline().strip().split(' ')))

AB = []
A = []
B = []

for i in range(n):
    t,a,b = list(map(int, stdin.readline().strip().split(' ')))
    if a == 1 and b == 1:
        AB.append(t)
    elif a == 1:
        A.append(t)
    elif b == 1:
        B.append(t)

AB.sort()
A.sort()
B.sort()

ans = 0
abi = 0
ai = 0
bi = 0
isPossible = True
for i in range(k):
    if abi == len(AB) and (ai == len(A) or bi == len(B)):
        isPossible = False
        break
    if abi == len(AB):
        ans += (A[ai] + B[bi])
        ai += 1
        bi += 1
        continue
    if ai == len(A) or bi == len(B):
        ans += AB[abi]
        abi += 1
        continue
    if A[ai] + B[bi] <= AB[abi]:
        ans += (A[ai] + B[bi])
        ai += 1
        bi += 1
        continue
    ans += AB[abi]
    abi += 1
    continue
if isPossible:
    print(ans)
else:
    print(-1)




import sys
input = sys.stdin.readline

n,k=list(map(int,input().split()))

BOOKS=[tuple(map(int,input().split())) for i in range(n)]

A=[]
B=[]
AB=[]

for t,a,b in BOOKS:
    if a==1 and b==1:
        AB.append(t)
    if a==1 and b==0:
        A.append(t)
    if a==0 and b==1:
        B.append(t)

A.sort()
B.sort()
AB.sort()

from itertools import accumulate

SA=[0]+list(accumulate(A))
SB=[0]+list(accumulate(B))
SAB=[0]+list(accumulate(AB))


ANS=1<<31

for i in range(len(SAB)):
    if 0<=k-i<len(SA) and 0<=k-i<len(SB):
        ANS=min(ANS,SAB[i]+SA[k-i]+SB[k-i])

if ANS==1<<31:
    print(-1)
else:
    print(ANS)

    


def solve():
    n, k = map(int,input().split())
    a1 = []
    b1 = []
    ab1 = []
    for i in range(n):
        t,a,b = map(int,input().split())
        if a == 1 and b == 1:
            ab1.append(t)
        elif a == 1:
            a1.append(t)
        elif b == 1:
            b1.append(t)
    a1.sort()
    b1.sort()
    for i in range(min(len(a1),len(b1))):
        ab1.append(a1[i]+b1[i])
    ab1.sort()
    p = 0
    qq = len(ab1)
    if qq < k:
        print(-1)
    else:
        ans = 0
        for i in range(k): ans += ab1[i]
        print(ans)
for i in range(1):
    solve()


n,k=list(map(int,input().split(" ")))
db=[]
a=[]
b=[]
for i in range(n):
    t,A,B= list(map(int, input().split(" ")))
    if A==B==1:
        db.append(t)
    elif A==1:
        a.append(t)
    elif B==1:
        b.append(t)
a.sort()
b.sort()
for i in range(min(len(a),len(b))):
    db.append((a[i]+b[i]))
if len(db)<k:
    print(-1)
else:
    db.sort()
    print(sum(db[:k]))


n, k = list(map(int, input().split()))
group = [[], [], [], []]
for i in range(n):
    t, a, b = list(map(int, input().split()))
    group[a * 2 + b].append(t)

pref_sum = [[0], [0], [0], [0]]
for g, ps in zip(group, pref_sum):
    g.sort()
    for i in g:
        ps.append(ps[-1] + i)

# print(group) 
# print(pref_sum) 
ans = 10**18
for i in range(min(k, len(group[3])) + 1):
    rest = k - i
    if rest > len(group[2]) or rest > len(group[1]):
        continue
    ans = min(ans, pref_sum[3][i] + pref_sum[1][rest] + pref_sum[2][rest])

if ans < 10**18:
    print(ans)
else:
    print(-1)





import sys, math,os
from io import BytesIO, IOBase
#data = BytesIO(os.read(0,os.fstat(0).st_size)).readline
# from bisect import bisect_left as bl, bisect_right as br, insort
# from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
# from itertools import permutations,combinations
# from decimal import Decimal
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write(' '.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
#sys.setrecursionlimit(100000 + 1)
INF = 10**9
mod = 998244353

n,k=mdata()
a,b,c,d=[],[],[],[]
for i in range(n):
    t1,a1,b1=mdata()
    if a1==1 and b1==1:
        c.append(t1)
    elif a1==1:
        a.append(t1)
    elif b1==1:
        b.append(t1)
    else:
        d.append(t1)
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
d.sort(reverse=True)
ans=0
while k:
    if len(a)!=0 and len(b)!=0:
        if len(c)!=0:
            if c[-1]<a[-1]+b[-1]:
                ans+=c.pop()
            else:
                ans+=a.pop()+b.pop()
        else:
            ans += a.pop() + b.pop()
    elif len(c)!=0:
        ans += c.pop()
    else:
        break
    k-=1
if k!=0:
    out(-1)
else:
    out(ans)



from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline
M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]


n,k = li()

alice = []
bob = []
both = []


for i in range(n):
    a,b,c = li()
    if b and c:
        both.append(a)
    elif b:alice.append(a)
    elif c:bob.append(a)


alice.sort()
bob.sort()


for i in range(min(len(alice),len(bob))):
    both.append(alice[i] + bob[i])


both.sort()
# print(both)
if len(both) < k:
    print(-1)
    return
else:print(sum(both[:k]))


#!/usr/bin/env pypy3

from sys import stdin, stdout
 
def input():
    return stdin.readline().strip()

N, K = input().split(' ')
N = int(N)
K = int(K)

alice_only = []
bob_only = []
both = []

for _ in range(N):
    t, a, b = input().split(' ')
    t = int(t)
    a = int(a)
    b = int(b)

    if a == 0 and b == 0: continue
    if a == 1 and b == 1: both += [t]
    if a == 1 and b == 0: alice_only += [t]
    if a == 0 and b == 1: bob_only += [t]

hybrid = []

alice_only = sorted(alice_only)
bob_only = sorted(bob_only)

for a, b in zip(alice_only, bob_only):
    hybrid += [a + b]

candidates = sorted(both + hybrid)

if len(candidates) < K:
    print(-1)
else:
    print(sum(candidates[0:K]))


import sys
input = sys.stdin.readline
n,minn = map(int,input().split())
a = []
ca, cb = 0, 0
for i in range(n):
	t,x,y = map(int,input().split())
	if x==1:
		ca += 1
	if y==1:
		cb += 1
	a.append((t,x,y))
if ca<minn or cb<minn:
	print (-1)
	return
ca,cb = 0,0
alice = []
bob = []
both = []
for i in range(n):
	if a[i][1]==a[i][2]==1:
		both.append(a[i][0])
	elif a[i][1]!=a[i][2]:
		if a[i][1]==1:
			alice.append(a[i][0])
		else:
			bob.append(a[i][0])
alice.sort()
bob.sort()
both.sort()
# print (alice)
# print (bob)
# print (both)
i,j,k = 0,0,0
ans = 0
while ca<minn or cb<minn:
	if (i<len(alice) and j<len(bob) and k<len(both)) and alice[i]+bob[j]<=both[k]:
		ans += alice[i]+bob[j]
		ca += 1
		cb += 1
		i += 1
		j += 1
	elif (i<len(alice) and j<len(bob) and k<len(both)) and alice[i]+bob[j]>=both[k]:
		ans += both[k]
		ca += 1
		cb += 1
		k += 1
	else:
		break

if i==len(alice):
	while ca<minn:
		ans += both[k]
		k += 1
		ca += 1
		cb += 1
if j==len(bob):
	while cb<minn:
		ans += both[k]
		k += 1
		ca += 1
		cb += 1
if k==len(both):
	while ca<minn:
		ans += alice[i]
		i += 1
		ca += 1
	while cb<minn:
		ans += bob[j]
		j += 1
		cb += 1
print (ans)

#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
both = []
alice = []
bob = []
for _ in range(n):
    c, a, b = map(int, input().split())
    if a and b:
        both.append(c)
    elif a:
        alice.append(c)
    elif b:
        bob.append(c)

alice.sort()
bob.sort()
for a, b in zip(alice, bob):
    both.append(a + b)
both.sort()

if len(both) < k:
    print(-1)
else:
    print(sum(both[:k]))

import sys
import math
def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return list(map(int, sys.stdin.readline().split()))

def SI():
	return sys.stdin.readline().strip()
n,k = MI()
x = []
y = []
z = []
o = []
for q in range(n):
	t,a,b = MI()
	if a == 1 and b == 1:
		z.append(t)
	elif a == 1:
		x.append(t)
	elif b == 1:
		y.append(t)
	else:
		o.append(t)
x.sort()
y.sort()
z.sort()
x0 = len(x)
y0 = len(y)
z0 = len(z)
if x0+z0<k or y0+z0<k:
	print(-1)
else:
	ans = 0
	l = r = 0
	for i in range(k):
		if l<x0 and l<y0 and r<z0:
			if x[l]+y[l]<z[r]:
				ans+=x[l]+y[l]
				l+=1
			else:
				ans+=z[r]
				r+=1
		elif r<z0:
			ans+=z[r]
			r+=1
		elif l<x0 and l<y0:
			ans+=x[l]+y[l]
			l+=1
	print(ans)


n, k = map(int, input().split())
A, B, both = [0], [0], [0]
for i in range(n):
	t, a, b = map(int, input().split())
	if a == 1 and b == 1:
		both.append(t)
	if a == 1 and b == 0:
		A.append(t)
	if a == 0 and b == 1:
		B.append(t)
A.sort()
B.sort()
both.sort()
if len(A)-1 + len(both)-1 < k or len(B)-1 + len(both)-1 < k:
	print(-1)
	return

for i in range(1, len(A)):
	A[i] += A[i-1]
for i in range(1, len(B)):
	B[i] += B[i-1]
cur = 0
ans = 10**12 + 10
for ch in range(len(both)):
	cur += both[ch]
	if ch > k:
		break
	# Need k - ch each from A and B
	if k - ch < len(A) and k - ch < len(B):
		ans = min(ans, A[k-ch] + B[k-ch] + cur)
print(ans)

import sys
n,k=map(int,input().split())
bothlike=[]
alike=[]
blike=[]
for i in range(n):
  t,a,b=map(int,input().split())
  if a==1 and b==1:
    bothlike.append(t)
  if a==1 and b==0:
    alike.append(t)
  if a==0 and b==1:
    blike.append(t)
if len(alike)+len(bothlike)<k or len(blike)+len(bothlike)<k:
  print(-1)
  return
alike.sort()
blike.sort()
bothlike.sort()
asum=[0]
current=0
for i in range(len(alike)):
  current+=alike[i]
  asum.append(current)
bsum=[0]
current=0
for i in range(len(blike)):
  current+=blike[i]
  bsum.append(current)
bothcurrent=0
ans=10**18
alen=len(alike)
blen=len(blike)
bothlen=len(bothlike)
for i in range(bothlen+1):
  if i>0:
    bothcurrent+=bothlike[i-1]
  if i>k:
    break
   
  if k-i>alen or k-i>blen:
    continue
  ans=min(ans,asum[k-i]+bsum[k-i]+bothcurrent)
print(ans)

n,k = map(int,input().split())
ablike = []
alike = []
blike = []
for i in range(n):
    t,a,b = map(int,input().split())
    if a == 1 and b == 1:
        ablike.append(t)
    elif a == 1:
        alike.append(t)
    elif b == 1:
        blike.append(t)
ablike.sort()
abtot = len(ablike)
alike.sort()
atot = len(alike)
blike.sort()
btot = len(blike)
x = min(atot,btot)
if abtot + x < k:
    print(-1)
else:
    p = k
    i = 0
    j = 0
    tot = 0
    while p > 0:
        if j < abtot and i < x:
            if ablike[j] <= (alike[i] + blike[i]):
                tot = tot + ablike[j]
                j = j + 1
                p = p - 1
            else:
                tot = tot + alike[i] + blike[i]
                i = i + 1
                p = p - 1
        elif j < abtot:
            tot = tot + ablike[j]
            j = j + 1
            p = p - 1
        else:
            tot = tot + alike[i] + blike[i]
            i = i + 1
            p = p - 1
    print(tot)

n, k = list(map(int, input().split()))
a, m, b = [], [], []
for i in range(n):
    ti, ai, bi = list(map(int, input().split()))
    if ai == 1 and bi == 1:
        m.append(ti)
    elif ai == 1:
        a.append(ti)
    elif bi == 1:
        b.append(ti)
a.sort()
m.sort()
b.sort()
pm = [0] * (len(m) + 1)
for i in range(1, len(m) + 1):
    pm[i] = pm[i - 1] + m[i - 1]
pa = [0] * (len(a) + 1)
for i in range(1, len(a) + 1):
    pa[i] = pa[i - 1] + a[i - 1]
pb = [0] * (len(b) + 1)
for i in range(1, len(b) + 1):
    pb[i] = pb[i - 1] + b[i - 1]            
ans = 10 ** 12
for c in range(min(k + 1, len(m) + 1)):
    if min(len(a), len(b)) >= k - c and ans > pm[c] + pa[k - c] + pb[k - c]:
        ans = pm[c] + pa[k - c] + pb[k - c]
if ans == 10 ** 12:
    print(-1)
else:
    print(ans)