Lena is preparing for an important coding competition that is preceded by a number of sequential preliminary contests. Initially, her luck balance is 0. She believes in "saving luck", and wants to check her theory. Each contest is described by two integers, $L[i]$ and $\boldsymbol{T[i]}$:

$L[i]$ is the amount of luck associated with a contest. If Lena wins the contest, her luck balance will decrease by $L[i]$; if she loses it, her luck balance will increase by $L[i]$.
$\boldsymbol{T[i]}$ denotes the contest's importance rating. It's equal to $\mbox{1}$ if the contest is important, and it's equal to $\mbox{0}$ if it's unimportant.

If Lena loses no more than $\boldsymbol{\mbox{k}}$ important contests, what is the maximum amount of luck she can have after competing in all the preliminary contests? This value may be negative.

Example 

$k=2$ 

$L=[5,1,4]$ 

$T=[1,1,0]$  

Contest		L[i]	T[i]
1		5	1
2		1	1
3		4	0

If Lena loses all of the contests, her will be $5+1+4=10$.  Since she is allowed to lose $2$ important contests, and there are only $2$ important contests, she can lose all three contests to maximize her luck at $10$.  

If $k=1$, she has to win at least $\mbox{1}$ of the $2$ important contests.  She would choose to win the lowest value important contest worth $\mbox{1}$.  Her final luck will be $5+4-1=8$.  

Function Description  

Complete the luckBalance function in the editor below.  

luckBalance has the following parameter(s):  

int k: the number of important contests Lena can lose  
int contests[n][2]: a 2D array of integers where each $contests[i]$ contains two integers that represent the luck balance and importance of the $i^{\mbox{th}}$ contest   

Returns   

int:  the maximum luck balance achievable   

Input Format

The first line contains two space-separated integers $n$ and $\boldsymbol{\mbox{k}}$, the number of preliminary contests and the maximum number of important contests Lena can lose. 

Each of the next $n$ lines contains two space-separated integers, $L[i]$ and $\boldsymbol{T[i]}$, the contest's luck balance and its importance rating.

Constraints

$1\leq n\leq100$
$0\leq k\leq N$
$1\leq L[i]\leq10^4$
$T[i]\in\{0,1\}$

Sample Input
STDIN       Function
-----       --------
6 3         n = 6, k = 3
5 1         contests = [[5, 1], [2, 1], [1, 1], [8, 1], [10, 0], [5, 0]]
2 1
1 1
8 1
10 0
5 0

Sample Output
29

Explanation

There are $n=6$ contests. Of these contests, $\begin{array}{c}4\end{array}$ are important and she cannot lose more than $k=3$ of them. Lena maximizes her luck if she wins the $3^{rd}$ important contest (where $L[i]=1$) and loses all of the other five contests for a total luck balance of $5+2+8+10+5-1=29$.

Difficulty: EASY
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
(N, K) = map(int, input().strip().split())
luck = 0
important = []
for i in range(N):
	(L, T) = list(map(int, input().strip().split()))
	if T == 0:
		luck += L
	else:
		important.append(L)
for i in sorted(important, reverse=True):
	if K > 0:
		luck += i
		K -= 1
	else:
		luck -= i
print(luck)


(n, k) = map(int, input().split())
b = 0
a = []
for i in range(n):
	(l, t) = map(int, input().split())
	if t:
		a.append(l)
	else:
		b += l
a.sort(key=lambda x: -x)
print(b + sum(a[:k]) - sum(a[k:]))


[N, K] = [int(a) for a in input().split()]
luck = 0
Ls = []
for i in range(N):
	[L, T] = [int(a) for a in input().split()]
	if T == 0:
		luck += L
	else:
		Ls.append(L)
K = len(Ls) - K
for i in sorted(Ls):
	if K > 0:
		K -= 1
		luck -= i
	else:
		luck += i
print(luck)


(N, K) = [int(s) for s in input().split()]
L = [0] * N
T = [0] * N
for i in range(0, N):
	(L[i], T[i]) = [int(s) for s in input().split()]
important_weights = sorted([L[i] for i in range(0, N) if T[i]])
n_imp = len(important_weights)
total_luck = sum(L)
for i in range(0, n_imp - K):
	total_luck -= 2 * important_weights[i]
print(total_luck)


(n, k) = [int(x) for x in input().split()]
s = 0
l = []
for i in range(n):
	(x, y) = [int(x) for x in input().split()]
	if y == 0:
		s += x
	else:
		l.append(x)
l.sort()
l.reverse()
i = min(k, len(l))
s += sum(l[:i])
s -= sum(l[i:])
print(s)


(n, k) = map(int, input().split(' '))
(imp, unimp) = ([], [])
for i in range(n):
	temp = input().split(' ')
	if temp[1] == '1':
		imp.append(int(temp[0]))
	else:
		unimp.append(int(temp[0]))
imp.sort(reverse=True)
luckbal = 0
for i in unimp:
	luckbal += i
for i in imp:
	if k:
		luckbal += i
		k -= 1
	else:
		luckbal -= i
print(luckbal)


(N, K) = map(int, input().split())
score = 0
important_luck = []
for i in range(N):
	(L, T) = map(int, input().split())
	if T == 1:
		important_luck.append(L)
	else:
		score += L
important_luck.sort(key=lambda x: -x)
score += sum(important_luck[:K])
score -= sum(important_luck[K:])
print(score)


(n, k) = map(int, input().split())
luck = 0
imp = []
for i in range(n):
	(l, t) = map(int, input().split())
	if t == 0:
		luck += l
	else:
		imp.append(l)
imp.sort()
imp.reverse()
for i in range(len(imp)):
	if k > 0:
		k -= 1
		luck += imp[i]
	else:
		luck -= imp[i]
print(luck)


(N, K) = [int(v) for v in input().split()]
contests = [[int(v) for v in input().split()] for Ni in range(N)]
important = list(sorted([c[0] for c in contests if c[1] == 1], reverse=True))
unimportant = [c[0] for c in contests if c[1] == 0]
L = sum(unimportant)
for i in important:
	if K > 0:
		K -= 1
		L += i
	else:
		L -= i
print(L)


(N, K) = map(int, input().split())
final_luck = 0
important_contests = []
for n in range(N):
	(luck, importance) = map(int, input().split())
	if importance == 0:
		final_luck += luck
	else:
		important_contests.append(luck)
important_contests.sort()
n_wins = len(important_contests) - K
for c in important_contests:
	if n_wins > 0:
		n_wins -= 1
		final_luck -= c
	else:
		final_luck += c
print(final_luck)


(N, K) = (int(i) for i in input().split(' '))
imp = []
luck = 0
for n in range(0, N):
	(l, t) = (int(i) for i in input().split(' '))
	if t == 0:
		luck += l
	else:
		imp.append(l)
imp = sorted(imp, reverse=True)
c = 0
for i in imp:
	if c < K:
		luck += i
		c += 1
	else:
		luck -= i
print(luck)


(N, K) = list(map(int, input().strip().split()))
U = []
I = []
for n in range(N):
	(L, T) = list(map(int, input().strip().split()))
	if T == 1:
		I.append(L)
	else:
		U.append(L)
luck = sum(U)
I = sorted(I, reverse=True)
numLost = 0
for val in I:
	if numLost < K:
		luck += val
		numLost += 1
	else:
		luck -= val
print(luck)


(x, y) = input().split()
(n, k) = (int(x), int(y))
sum = 0
arr = []
for i in range(n):
	(x, y) = input().split()
	(l, t) = (int(x), int(y))
	if t == 0:
		sum += l
	else:
		arr.append(l)
arr.sort()
for i in range(len(arr)):
	if i < len(arr) - k:
		sum -= arr[i]
	else:
		sum += arr[i]
print(sum)


(n, k) = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n)]
l.sort(key=lambda x: (x[1], x[0]))
res = 0
i = 0
while i < n and l[i][1] == 0:
	res += l[i][0]
	i += 1
i = n - 1
while i >= 0 and l[i][1] == 1 and (n - i <= k):
	res += l[i][0]
	i -= 1
while i >= 0 and l[i][1] == 1:
	res -= l[i][0]
	i -= 1
print(res)


(n, k) = map(int, input().split())
ans = 0
imp = []
for ii in range(n):
	(l, t) = map(int, input().split())
	if t == 0:
		ans += l
	else:
		imp.append(l)
imp = sorted(imp, reverse=True)
for l in imp:
	if k > 0:
		ans += l
		k -= 1
	else:
		ans -= l
print(ans)


(n, k) = [int(i) for i in input().strip().split(' ')]
tl = 0
imp = []
for each in range(n):
	(l, t) = [int(i) for i in input().strip().split(' ')]
	if t == 0:
		tl += l
	else:
		imp.append(l)
imp.sort(reverse=True)
tl += sum(imp[:k]) - sum(imp[k:])
print(tl)


(N, K) = map(int, input().split())
K = min(K, N)
luck = 0
temp = []
for _ in range(N):
	(L, T) = map(int, input().split())
	if T == 0:
		luck += L
	else:
		temp.append(L)
temp.sort(reverse=True)
luck = luck + sum(temp[:K]) - sum(temp[K:])
print(luck)


(n, k) = list(map(int, input().split()))
l = []
for i in range(n):
	l.append(list(map(int, input().split())))
l = sorted(l, reverse=True)
luck = 0
for i in l:
	if not i[1]:
		luck += i[0]
	elif not k:
		luck -= i[0]
	else:
		luck += i[0]
		k -= 1
print(luck)


(n, k) = input().strip().split()
(n, k) = (int(n), int(k))
imp = []
notImp = []
for i in range(n):
	(l, t) = input().strip().split()
	(l, t) = (int(l), int(t))
	if t == 1:
		imp.append(l)
	else:
		notImp.append(l)
finalLuck = sum(notImp)
while len(imp) > k:
	i = imp.index(min(imp))
	finalLuck -= imp[i]
	del imp[i]
finalLuck += sum(imp)
print(finalLuck)


(N, K) = list(map(int, input().split()))
important_contests = []
residual_luck = 0
for i in range(N):
	(L, T) = list(map(int, input().split()))
	if T == 0:
		residual_luck += L
	else:
		important_contests.append(L)
important_contests.sort(reverse=True)
for (i, val) in enumerate(important_contests):
	if i >= K:
		residual_luck -= val
	else:
		residual_luck += val
print(residual_luck)


(n, k) = [int(i) for i in input().strip().split()]
c = []
lb = 0
for __ in range(n):
	inp = [int(i) for i in input().strip().split()]
	if inp[1] == 0:
		lb = lb + inp[0]
	else:
		c.append(inp[0])
c.sort()
if k <= len(c):
	lb = lb - sum(c[:len(c) - k]) + sum(c[len(c) - k:])
else:
	lb = lb + sum(c)
print(lb)


(n, k) = [int(x) for x in input().split()]
contest = []
for _ in range(n):
	contest += [[int(x) for x in input().split()]]
contest.sort(reverse=True)
luck = 0
for j in range(n):
	if contest[j][1] == 0:
		luck += contest[j][0]
	elif k > 0:
		luck += contest[j][0]
		k -= 1
	else:
		luck -= contest[j][0]
print(luck)


from heapq import heappush, heappop
(n, k) = (int(num) for num in input().split())
luck = 0
luck_hq = []
for _ in range(n):
	(l, t) = (int(num) for num in input().split())
	if t == 0:
		luck += l
	else:
		heappush(luck_hq, -l)
if k >= len(luck_hq):
	luck += -sum(luck_hq)
else:
	for _ in range(k):
		luck += -heappop(luck_hq)
	luck += sum(luck_hq)
print(luck)


(N, K) = map(int, input().split())
contests = [[], []]
for n in range(N):
	(L, T) = map(int, input().split())
	contests[T].append(L)
contests[1].sort()
W = len(contests[1])
if W > K:
	S = sum(contests[0]) + sum(contests[1][W - K:]) - sum(contests[1][:W - K])
else:
	S = sum(contests[0]) + sum(contests[1])
print(S)


(N, K) = map(int, input().strip().split())
A = []
ans = 0
for n in range(N):
	(a, b) = map(int, input().strip().split())
	if b & 1:
		A.append(a)
	else:
		ans += a
n = len(A)
if n <= K:
	ans += sum(A)
else:
	A.sort()
	A = A[::-1]
	ans = ans + sum(A[:K]) - sum(A[K:])
print(ans)


(N, K) = map(int, input().strip().split())
a = []
luck = 0
for n in range(N):
	(L, T) = map(int, input().strip().split())
	if T == 0:
		luck += L
	else:
		a.append(L)
lena = len(a)
if lena <= K:
	luck += sum(a)
else:
	a.sort()
	luck += sum(a[lena - K:])
	luck -= sum(a[:lena - K])
print(luck)


(n, k) = [int(x) for x in input().split(' ')]
important = []
luck = 0
for i in range(n):
	(l, t) = [int(x) for x in input().split(' ')]
	if t:
		important.append(l)
	else:
		luck += l
important.sort(reverse=True)
luck += sum(important[:k])
luck -= sum(important[k:])
print(luck)


(contests, maxImportantLosses) = [int(n) for n in input().strip().split()]
luck = 0
important = []
for i in range(contests):
	(value, isImportant) = [int(n) for n in input().strip().split()]
	if isImportant == 1:
		important.append(value)
	else:
		luck += value
important.sort()
losses = 0
i = len(important) - 1
while i >= 0:
	if losses < maxImportantLosses:
		luck += important[i]
	else:
		luck -= important[i]
	losses += 1
	i -= 1
print(luck)


import sys
f = sys.stdin
[N, K] = [int(x) for x in f.readline().rstrip().split()]
important = []
luck_balance = 0
for _ in range(N):
	[L, I] = [int(x) for x in f.readline().rstrip().split()]
	if I == 1:
		important.append(L)
	else:
		luck_balance += L
sorted_important = sorted(important, reverse=True)
number_of_contest_to_lose = min(len(sorted_important), K)
for i in range(number_of_contest_to_lose):
	luck_balance += sorted_important[i]
for i in range(number_of_contest_to_lose, len(sorted_important)):
	luck_balance -= sorted_important[i]
print(luck_balance)


(N, K) = [int(x) for x in input().split()]
total = 0
importants = []
for _ in range(N):
	(L, T) = [int(x) for x in input().split()]
	if T == 0:
		total += L
	else:
		importants.append(L)
importants.sort(reverse=True)
print(total + sum(importants[:K]) - sum(importants[K:]))


(n, k) = map(int, input().split())
contests = []
for _ in range(n):
	(l, t) = map(int, input().split())
	k -= t
	contests.append((l, t))
k = max(-k, 0)
contests.sort(key=lambda x: (-x[1], x[0]))
c = [x[0] for x in contests]
print(sum(c[k:]) - sum(c[:k]))


(N, K) = map(int, input().split(' '))
L = []
T = []
luck = 0
for i in range(N):
	(li, ti) = map(int, input().split(' '))
	if ti == 0:
		luck += li
	else:
		L.append(li)
L.sort(reverse=True)
luck += sum(L[:K]) - sum(L[K:])
print(luck)


(n, k) = map(int, input().split())
(ans, l) = (0, [])
for _ in range(n):
	(L, T) = map(int, input().split())
	if T:
		l += [L]
	else:
		ans += L
l.sort(reverse=True)
print(ans + sum(l[:k]) - sum(l[k:]))


def get_ints():
	return [int(x) for x in input().strip().split(' ')]
(N, K) = get_ints()
L = []
total_luck = 0
for i in range(N):
	(luck, t) = get_ints()
	if t == 0:
		total_luck += luck
	else:
		L.append(luck)
L = sorted(L)[::-1]
while len(L) > K:
	total_luck -= L.pop()
total_luck += sum(L)
print(total_luck)


(N, K) = map(int, input().strip().split(' '))
L = []
luck = 0
for i in range(N):
	(l, t) = map(int, input().strip().split(' '))
	if t:
		L.append(l)
	else:
		luck += l
L.sort(reverse=True)
luck += sum(L[:K]) - sum(L[K:])
print(luck)


nk = list(map(int, input().split()))
contests = []
won = [0]
for c in range(nk[0]):
	contests.append(list(map(int, input().split())))
important = [a for [a, b] in contests if b == 1]
important.sort()
for i in range(len(important) - nk[1]):
	won.append(important.pop(0))
print(sum([a for [a, b] in contests if b == 0]) + sum(important) - sum(won))


(n, k) = map(int, input().split())
imp = []
s = 0
for x in range(n):
	(a, b) = map(int, input().split())
	if b == 1:
		imp.append(a)
	else:
		s += a
imp = sorted(imp, reverse=True)
s += sum(imp[:k]) - sum(imp[k:])
print(s)


(N, K) = map(int, input().split())
important = []
cum_luck = 0
for _ in range(N):
	(li, ti) = map(int, input().split())
	if ti:
		important.append(li)
	else:
		cum_luck += li
important.sort(reverse=True)
for (i, luck) in enumerate(important):
	if i < K:
		cum_luck += luck
	else:
		cum_luck -= luck
print(cum_luck)


(n, k) = input().strip().split()
(n, k) = (int(n), int(k))
totalLuck = 0
importantLucks = []
importantLuckCount = 0
for i in range(n):
	(li, ti) = input().strip().split()
	if ti == '0':
		totalLuck += int(li)
	else:
		importantLucks.append(int(li))
		importantLuckCount += 1
importantLucks = sorted(importantLucks, reverse=True)
while importantLuckCount > k:
	totalLuck -= importantLucks[importantLuckCount - 1]
	importantLucks = importantLucks[:importantLuckCount - 1]
	importantLuckCount -= 1
for l in importantLucks:
	totalLuck += l
print(totalLuck)


(N, K) = map(int, input().split())
luck = 0
important = []
for i in range(N):
	(L, T) = map(int, input().split())
	if T == 0:
		luck += L
	else:
		important.append(L)
important = sorted(important, reverse=True)
index = 0
while index < len(important) and K > 0:
	luck += important[index]
	index += 1
	K -= 1
for Li in important[index:]:
	luck -= Li
print(luck)


from heapq import heappush, heappop
(N, K) = map(int, input().split())
(count, counti, stack) = (0, 0, [])
for _ in range(N):
	(l, t) = map(int, input().split())
	count += l
	if t == 1:
		counti += 1
		heappush(stack, -l)
while stack and len(stack) > counti - K:
	heappop(stack)
print(count + 2 * sum(stack))


(n, k) = input().strip().split()
(n, k) = [int(n), int(k)]
imp = []
notimp = 0
for i in range(n):
	(l, t) = input().strip().split()
	(l, t) = [int(l), int(t)]
	if t == 0:
		notimp += l
	else:
		imp.append(l)
imp.sort(reverse=True)
print(notimp + sum(imp[:k]) - sum(imp[k:]))


from operator import itemgetter
(n, k) = [int(i) for i in input().split()]
imp = []
unimp = []
for i in range(n):
	(l, t) = [int(j) for j in input().split()]
	if t == 1:
		imp.append([l, t])
	else:
		unimp.append([l, t])
ans = 0
for i in unimp:
	ans += i[0]
imp.sort(key=itemgetter(0))
imp.reverse()
length = len(imp)
minimum = min([k, length])
for i in range(minimum):
	ans += imp[i][0]
for i in range(minimum, length):
	ans -= imp[i][0]
print(ans)


(n, k) = [int(x) for x in input().split(' ')]
a = []
luck = 0
while n:
	n -= 1
	(l, i) = [int(x) for x in input().split(' ')]
	if i:
		a.append(l)
	else:
		luck += l
a = sorted(a, key=int, reverse=True)
for x in a:
	if k:
		k -= 1
		luck += x
	else:
		luck -= x
print(luck)


from fileinput import input
data = []
for line in input():
	data.append(map(int, line.strip().split()))
(N, K) = data[0]
total = 0
importants = []
for i in range(N):
	(L, I) = data[1 + i]
	if I is 1:
		importants.append(L)
	else:
		total += L
importants.sort()
for i in range(len(importants)):
	if K > 0:
		total += importants[-(i + 1)]
		K -= 1
	else:
		total -= importants[-(i + 1)]
print(total)


(N, K) = map(int, input().split())
luck = 0
ls = []
for _ in range(N):
	(L, T) = map(int, input().split())
	if T == 0:
		luck += L
	else:
		ls.append(L)
ls.sort()
ls.reverse()
luck = luck + sum(ls[:K]) - sum(ls[K:])
print(luck)


from sys import stdin, maxsize
data = stdin.readline().strip().split(' ')
n = int(data[0])
k = int(data[1])
important = []
unimportant = []
for i in range(n):
	test = stdin.readline().strip().split(' ')
	if int(test[1]) == 1:
		important.append(int(test[0]))
	else:
		unimportant.append(int(test[0]))
important.sort()
important = list(reversed(important))
result = 0
i = 0
for test in important:
	result += test if i < k else -test
	i += 1
print(result + sum(unimportant))


NK = input()
(N, K) = NK.split(' ')
(N, K) = (int(N), int(K))
total = 0
Ls = []
for n in range(N):
	(L, I) = input().split(' ')
	(L, I) = (int(L), int(I))
	if I == 1:
		Ls.append(L)
	else:
		total += L
Ls.sort(key=lambda x: -x)
M = len(Ls)
for k in range(min(M, K)):
	total += Ls[k]
for k in range(K, M):
	total -= Ls[k]
print(total)


(N, K) = input().split(' ')
(N, K) = (int(N), int(K))
important_contests = []
luck_balance = 0
for i in range(N):
	(L, T) = input().split(' ')
	(L, T) = (int(L), int(T))
	if T == 1:
		important_contests.append(L)
	else:
		luck_balance += L
remaining_losses_allowed = K
for contest_score in sorted(important_contests, reverse=True):
	if remaining_losses_allowed < 1:
		luck_balance -= contest_score
	else:
		luck_balance += contest_score
		remaining_losses_allowed -= 1
print(luck_balance)


(N, K) = map(int, input().strip().split())
contests = []
contestsi = []
contestsu = []
for i in range(N):
	contests += [[int(i) for i in input().strip().split()]]
contestsi = [i for (i, j) in contests if j == 1]
contestsu = [i for (i, j) in contests if j == 0]
contestsi = sorted(contestsi, reverse=True)
ans = sum(contestsu) + sum(contestsi[:K]) - sum(contestsi[K:])
print(ans)


(t, k) = [int(i) for i in input().split(' ')]
imp = []
notimp = []
luck = 0
for a0 in range(t):
	(i, j) = [int(i) for i in input().split(' ')]
	if j == 1:
		imp += [i]
	else:
		notimp += [i]
imp.sort(reverse=True)
for i in range(len(imp)):
	kcheck = i + 1
	if kcheck <= k:
		luck += imp[i]
	else:
		luck -= imp[i]
for i in notimp:
	luck += i
print(luck)


(n, maxImpLose) = [int(i) for i in input().split(' ')]
unimpContests = []
impContests = []
for i in range(n):
	(l, t) = [int(i) for i in input().split(' ')]
	if t == 1:
		impContests.append(l)
	else:
		unimpContests.append(l)
balance = 0
balance += sum(unimpContests)
impContests.sort(reverse=True)
impContestsWin = impContests[maxImpLose:]
impContestsLose = impContests[:maxImpLose]
balance -= sum(impContestsWin)
balance += sum(impContestsLose)
print(balance)


(N, K) = list(map(int, input().strip().split()))
important = []
unimportant = []
for _ in range(N):
	(L_i, T_i) = list(map(int, input().strip().split()))
	if T_i == 0:
		unimportant.append(L_i)
	else:
		important.append(L_i)
important.sort()
unimportant.sort()
luck = 0
num_lost = 0
while len(important) > 0 and num_lost < K:
	luck += important.pop()
	num_lost += 1
luck -= sum(important)
luck += sum(unimportant)
print(luck)


(N, K) = input().strip().split(' ')
(N, K) = [int(N), int(K)]
imp = []
non_imp = []
for i in range(N):
	(l, t) = input().strip().split(' ')
	(l, t) = [int(l), int(t)]
	if t == 1:
		imp.append(l)
	else:
		non_imp.append(l)
luck = sum(non_imp)
imp.sort()
imp.reverse()
count = 0
for i in range(len(imp)):
	if count < K:
		luck += imp[i]
		count += 1
	else:
		luck -= imp[i]
print(luck)


def find_min_important(l, t, used):
	minV = float('inf')
	best = -1
	for i in range(len(t)):
		if t[i] == 1 and used[i] == False:
			if l[i] < minV:
				minV = l[i]
				best = i
	if best != -1:
		used[best] = True
	return minV

def main():
	(n, k) = (int(x) for x in input().split())
	l = []
	t = []
	used = []
	for i in range(n):
		used.append(False)
		(li, ti) = (int(x) for x in input().split())
		l.append(li)
		t.append(ti)
	max_luck = sum(l)
	important_losses = sum(t)
	while important_losses > k:
		max_luck -= 2 * find_min_important(l, t, used)
		important_losses -= 1
	print(max_luck)
main()


from sys import stderr
from heapq import heappop, heappush

def read(f):
	return f(input())

def readlist(f):
	return [f(x) for x in input().split()]
(N, K) = readlist(int)
sumL = 0
lostT1 = []
for i in range(N):
	(L, T) = readlist(int)
	if T == 0:
		sumL += L
	else:
		heappush(lostT1, L)
		if len(lostT1) > K:
			sumL -= heappop(lostT1)
print(sumL + sum(lostT1))


(N, K) = map(int, input().strip().split(' '))
luck = 0
arr = []
for x in range(N):
	(a, b) = map(int, input().strip().split(' '))
	if b == 0:
		luck += a
	else:
		arr.append(a)
arr.sort()
arr = arr[::-1]
try:
	luck += sum(arr[:K])
except IndexError:
	luck += sum(arr)
loss = 0
try:
	loss = sum(arr[K:])
except IndexError:
	pass
print(luck - loss)


(n, k) = map(int, input().split())
l_list = []
st = 0
for _ in range(n):
	(l, t) = map(int, input().split())
	if t == 1:
		l_list.append(l)
	else:
		st += l
l_list.sort(reverse=True)
print(sum(l_list[:k]) + st - sum(l_list[k:]))


(numContests, maxLoss) = input().strip().split(' ')
(numContests, maxLoss) = [int(numContests), int(maxLoss)]
unimp = []
imp = []
totalLuck = 0
for i in range(numContests):
	(luck, importance) = input().strip().split(' ')
	(luck, importance) = [int(luck), int(importance)]
	if importance == 1:
		imp.append(luck)
	else:
		unimp.append(luck)
unimp = sorted(unimp)
imp = sorted(imp)
while len(imp) > maxLoss:
	currLoss = imp.pop(0)
	totalLuck -= currLoss
for i in range(len(imp)):
	totalLuck += imp[i]
for j in range(len(unimp)):
	totalLuck += unimp[j]
print(totalLuck)


raw = [int(s) for s in input().split(' ')]
(n, k) = (raw[0], raw[1])
ones = []
zeros = []
luck = 0
for _ in range(n):
	raw = [int(s) for s in input().split(' ')]
	(l, t) = (raw[0], raw[1])
	luck += l
	if t == 1:
		ones.append(l)
	else:
		zeros.append(l)
diff = len(ones) - k
for _ in range(diff):
	sub = min(ones)
	ones.remove(sub)
	luck -= sub * 2
print(luck)


(N, K) = input().strip().split(' ')
(N, K) = [int(N), int(K)]
Larray = []
Tarray = []
L_important = []
luck = 0
for x in range(N):
	(L, T) = input().strip().split(' ')
	(L, T) = [int(L), int(T)]
	Larray.append(L)
	Tarray.append(T)
for x in range(N):
	if Tarray[x] == 0:
		luck += Larray[x]
	else:
		L_important.append(Larray[x])
L_important.sort()
L_important.reverse()
for x in range(len(L_important)):
	if x < K:
		luck += L_important[x]
	else:
		luck -= L_important[x]
print(luck)


(n, k) = map(int, input().split())
arr = [[0 for x in range(2)] for x in range(n)]
imp = [] * n
result = 0
for i in range(n):
	(arr[i][0], arr[i][1]) = map(int, input().split())
for i in range(n):
	if arr[i][1] == 0:
		result += arr[i][0]
	else:
		imp.append(arr[i][0])
for i in range(len(imp) - k):
	number = min(imp)
	result -= number
	imp.remove(number)
for i in range(len(imp)):
	result += imp[i]
print(result)


(N, K) = map(int, input().split())
importants = []
balance = 0
for _ in range(N):
	(l, t) = map(int, input().split())
	if t == 0:
		balance += l
	else:
		importants.append((l, t))
I = len(importants)
if I <= K:
	for contest in importants:
		balance += contest[0]
else:
	importants.sort(key=lambda x: x[0])
	for i in range(I):
		if i < I - K:
			balance -= importants[i][0]
		else:
			balance += importants[i][0]
print(balance)


(N, K) = [int(x) for x in input().strip().split(' ')]
L1 = []
L0 = []
for i in range(N):
	(l, t) = [int(x) for x in input().strip().split(' ')]
	if t == 0:
		L0.append(l)
	else:
		L1.append(l)
n1 = len(L1)
n0 = len(L0)
if n1 > 0 and n1 > K:
	L1.sort()
s = 0
if n1 > 0:
	s = sum(L1)
if n0 > 0:
	s += sum(L0)
n = n1 - K
sm = 0
if n > 0:
	sm = sum(L1[0:n])
s = s - 2 * sm
print(s)


import sys
(N, K) = input().strip().split(' ')
N = int(N)
K = int(K)
sum_var = 0
list_imp = []
for i in range(N):
	(l, t) = input().strip().split(' ')
	(l, t) = [int(l), int(t)]
	sum_var += l
	if t == 1:
		list_imp.append(l)
poss_lose = len(list_imp) - K
if poss_lose <= 0:
	print(sum_var)
else:
	for i in range(poss_lose):
		mini = min(list_imp)
		list_imp.remove(mini)
		sum_var -= 2 * mini
	print(sum_var)


a = True
(n, l) = input().strip().split(' ')
(n, l) = [int(n), int(l)]
imp = []
mini = [10 ** 4 + 1] * l
bigmin = 10 ** 4 + 1
total = 0
for x in range(n):
	d = input()
	(luck, importance) = d.strip().split(' ')
	if int(importance) == 0:
		total += int(luck)
	else:
		imp.append(int(luck))
imp = sorted(imp)
for x in range(0, len(imp)):
	if x < len(imp) - l:
		total -= imp[x]
	else:
		total += imp[x]
print(total)


(N, K) = input().strip().split(' ')
(N, K) = [int(N), int(K)]
imp = []
luck = 0
for i in range(N):
	(l, t) = input().strip().split(' ')
	(l, t) = [int(l), int(t)]
	if t == 1:
		imp.append(l)
	if t == 0:
		luck = luck + l
imps = sorted(imp)
d = len(imps) - K
for i in range(len(imps)):
	if i >= d:
		luck = luck + imps[i]
	else:
		luck = luck - imps[i]
print(luck)


(N, K) = map(int, input().split())
important = []
notImportant = []
for _ in range(N):
	(L, T) = map(int, input().split())
	if T:
		important.append(L)
	else:
		notImportant.append(L)
important.sort(reverse=True)
print(sum(notImportant) + sum(important[:K]) - sum(important[K:]))


(n, k) = input().split()
(n, k) = [int(n), int(k)]
luck = 0
con = []
for i in range(n):
	(l, t) = input().split()
	l = int(l)
	if t == '0':
		luck += l
	else:
		con.append(l)
for a in sorted(con, reverse=True):
	if k > 0:
		luck += a
		k -= 1
	else:
		luck -= a
print(luck)


firstline = input().split()
n = int(firstline[0])
k = int(firstline[1])
contests = []
numimportantcontests = 0
for num in range(n):
	split = input().split()
	contests.append([int(split[0]), int(split[1])])
	if split[1] == '1':
		numimportantcontests = numimportantcontests + 1

def getkey(item):
	return item[0]
luck = 0
if n <= k:
	for contest in contests:
		luck = luck + int(contest[0])
	print(luck)
else:
	sortedcontests = sorted(contests, key=getkey)
	contestslost = 0
	conteststolose = numimportantcontests - k
	for contest in sortedcontests:
		if int(contest[1]) == 0:
			luck = luck + contest[0]
		elif contestslost < conteststolose:
			luck = luck - contest[0]
			conteststolose = conteststolose - 1
		else:
			luck = luck + contest[0]
	print(luck)


import sys

def get_input_tuple():
	(a, b) = input().strip().split(' ')
	return (int(a), int(b))
important_contests = []
total_luck = 0
(n, k) = get_input_tuple()
for i in range(n):
	(l, t) = get_input_tuple()
	if t == 1:
		important_contests.append(l)
	else:
		total_luck += l
important_contests = sorted(important_contests, reverse=True)
total_luck += sum(important_contests[:k])
total_luck -= sum(important_contests[k:])
print(total_luck)


from functools import reduce
from operator import itemgetter
(n, k) = map(int, input().strip().split(' '))
contests = [input() for i in range(n)]
pairs = [[int(s) for s in c.split(' ')] for c in contests]
lucks = sorted(pairs, key=itemgetter(1, 0), reverse=True)
not_importants = [l[0] for l in lucks if l[1] == 0]
importants = [l[0] for l in lucks if l[1] == 1]
score = sum(not_importants)
score += sum([i for i in importants[:k]])
score -= sum([i for i in importants[k:]])
print(score)


tests = [int(n) for n in input().split(' ')]
cases = [[] for n in range(2)]
for t in range(tests[0]):
	num = [int(n) for n in input().split(' ')]
	cases[num[1]].append(num[0])
else:
	cases[1] = sorted(cases[1], reverse=True)
	print(sum(cases[0]) + sum(cases[1][:tests[1]]) - sum(cases[1][tests[1]:]))


(N, K) = [int(i) for i in input().split()]
cases = [[int(i) for i in input().split()] for i in range(N)]
(luck, important) = (0, [])
for c in cases:
	if c[1] == 0:
		luck += c[0]
	else:
		important.append(c[0])
important.sort(reverse=True)
for l in important:
	if K > 0:
		luck += l
		K -= 1
	else:
		luck -= l
print(luck)


def main():
	(n, k) = [int(x) for x in input().strip().split(' ')]
	competition_list = []
	for i in range(n):
		competition_list.append([int(x) for x in input().strip().split(' ')])
	competition_list.sort(key=lambda x: x[0], reverse=True)
	luck = 0
	for x in competition_list:
		if k > 0:
			luck += x[0]
			if x[1] == 1:
				k -= 1
		elif x[1] == 1:
			luck -= x[0]
		else:
			luck += x[0]
	print(luck)
main()


(N, K) = input().strip().split(' ')
(N, K) = [int(N), int(K)]
T1 = []
totalL = 0
for ii in range(N):
	(L, T) = input().strip().split(' ')
	(L, T) = [int(L), int(T)]
	if T == 0:
		totalL += L
	else:
		T1.append(L)
T1.sort()
F = len(T1) - K
if F < 0:
	F = 0
for ii in range(F):
	totalL -= T1[ii]
for ii in range(F, len(T1)):
	totalL += T1[ii]
print(totalL)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
luck = 0
li = []
lmin = 3222222222
for i in range(0, n):
	(l, t) = input().strip().split(' ')
	(l, t) = [int(l), int(t)]
	if t == 0:
		luck += l
	else:
		li.append(l)
li.sort(reverse=True)
for l in li:
	if k == 0:
		luck -= l
	else:
		k -= 1
		luck += l
print(luck)


import heapq
(N, K) = [int(num) for num in input().split()]
important_contests = []
remaining_contests = []
for i in range(N):
	(L, T) = [int(num) for num in input().split()]
	if T == 1:
		important_contests.append((L, T))
	else:
		remaining_contests.append((L, T))
important_to_lose = heapq.nlargest(K, important_contests, key=lambda contest: contest[0])
important_to_win = [contest for contest in important_contests if contest not in important_to_lose]
luck = sum([contest[0] for contest in important_to_lose]) + sum([contest[0] for contest in remaining_contests]) - sum([contest[0] for contest in important_to_win])
print(luck)


(n, k) = map(int, input().strip().split())
a = []
b = []
(c, d) = (0, 0)
for i in range(n):
	(x, y) = map(int, input().strip().split())
	if y == 1:
		a.append(x)
		c += 1
	else:
		b.append(x)
		d += 1
a.sort()
a.reverse()
ans = 0
for i in range(d):
	ans += b[i]
d = 0
for i in range(c):
	if d < k:
		ans += a[i]
		d += 1
	else:
		ans -= a[i]
print(ans)


(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
onescore = []
zeroscore = []
for i in range(n):
	(score, important) = [int(each) for each in input().strip().split(' ')]
	if important == 1:
		onescore.append(score)
	else:
		zeroscore.append(score)
removal = []
while len(onescore) > k:
	m = min(onescore)
	onescore.remove(m)
	removal.append(m)
print(sum(onescore) + sum(zeroscore) - sum(removal))


import sys
x = input().split()
n = int(x[0])
k = int(x[1])
lst = []
l1 = []
l2 = []
for i in range(n):
	y = input().split()
	lst.append((int(y[0]), int(y[1])))
lst.sort(reverse=True)
for j in range(n):
	if lst[j][1] == 1:
		l1.append(lst[j][0])
	else:
		l2.append(lst[j][0])
c = 0
c1 = 0
if len(l1) <= k:
	c += sum(l1) + sum(l2)
	print(c)
else:
	for m in range(k):
		c += l1[m]
	for n in range(len(l1) - k):
		c1 += l1[n + k]
	c += sum(l2)
	c -= c1
	print(c)


[N, K] = [int(u) for u in input().strip().split(' ')]
import collections
luck = collections.Counter()
important = []
unimportant = []
for _ in range(N):
	[L, T] = [int(u) for u in input().strip().split(' ')]
	if T == 1:
		important.append(L)
	else:
		unimportant.append(L)
K = len(important) - K
if K < 0:
	K = 0
hold = []
imps = []
for i in important:
	if i < 0:
		hold.append(i)
	else:
		imps.append(i)
imps.sort()
if len(hold) > K:
	K = 0
else:
	K -= len(hold)
Total = sum(hold)
Total = Total - sum(imps[:K]) + sum(imps[K:])
Total = Total + sum(unimportant)
print(Total)


(n, k) = map(int, input().split())
luck_amount = 0
contests = []
for i in range(n):
	(l, t) = map(int, input().split())
	if t == 0:
		luck_amount += l
		continue
	contests.append([l, t])
contests.sort(key=lambda x: x[0])
while len(contests) > k:
	minimal = contests.pop(0)
	luck_amount -= minimal[0]
for i in contests:
	luck_amount += i[0]
print(luck_amount)


import sys
(N, K) = input().strip().split(' ')
(N, K) = [int(N), int(K)]
L0 = []
L1 = []
for i in range(0, N):
	(Li, Ti) = input().strip().split(' ')
	(Li, Ti) = [int(Li), int(Ti)]
	if Ti == 0:
		L0.append(Li)
	else:
		L1.append(Li)
SortL1 = sorted(L1, reverse=True)
print(sum(L0) + sum(SortL1[:K]) - sum(SortL1[K:]))


(N, K) = [int(x) for x in input().split()]
not_important = 0
arr = []
total = 0
for _ in range(N):
	(luck, imp) = [int(x) for x in input().split()]
	if imp == 0:
		total += luck
	else:
		arr.append(luck)
arr = sorted(arr, reverse=True)
print(total + sum(arr[:K]) - sum(arr[K:]))


import sys
(n, k) = input().split(' ')
(n, k) = (int(n), int(k))
a = [[int(jj) for jj in input().split(' ')] + [1] for j in range(n)]
a.sort(key=lambda a: a[0])
a.sort(key=lambda a: a[1], reverse=True)
i_num = sum([b[1] for b in a])
w_num = i_num - k
for i in range(w_num):
	a[i][2] = -1
luck_sum = sum([b[0] * b[2] for b in a])
print(luck_sum)


L = 0
i = str(input()).split()
N = int(i[0])
K = int(i[1])
arr = {0: list(), 1: list()}
for j in range(0, N):
	i = str(input()).split()
	arr[int(i[1])].append(int(i[0]))
for i in range(0, len(arr[1]) - K):
	if len(arr[1]) > 0:
		L -= min(arr[1])
		arr[1].remove(min(arr[1]))
	else:
		L -= min(arr[0])
		arr[0].remove(min(arr[1]))
for v in arr[0]:
	L += v
for v in arr[1]:
	L += v
print(L)


from functools import reduce

def unpack_line():
	return input().strip().split()

def main():
	(N_tmp, K_tmp) = unpack_line()
	(N, K) = (int(N_tmp), int(K_tmp))
	important_contest_luck = []
	saved_up_luck = 0
	for dummy in range(N):
		(L_tmp, T_tmp) = unpack_line()
		(L, T) = (int(L_tmp), int(T_tmp))
		if T == 0:
			saved_up_luck += L
		else:
			important_contest_luck.append(L)
	important_contest_luck.sort(reverse=True)
	saved_up_luck = reduce(lambda x, y: x + y, important_contest_luck[:K], saved_up_luck)
	saved_up_luck = reduce(lambda x, y: x - y, important_contest_luck[K:], saved_up_luck)
	return saved_up_luck
print(main())


(n, k) = [int(i) for i in input().strip().split(' ')]
c = []
for i in range(n):
	c.append([int(i) for i in input().strip().split(' ')])
im = []
uim = []
for i in c:
	if i[1] == 1:
		im.append(i)
	else:
		uim.append(i)
im.sort(key=lambda i: i[0])
l = 0
mw = len(im) - k
for i in im:
	if mw > 0:
		l -= i[0]
		mw -= 1
	else:
		l += i[0]
for i in uim:
	l += i[0]
print(l)


import itertools
(N, K) = input().strip().split(' ')
(N, K) = [int(N), int(K)]
important = []
luck = 0
for _ in itertools.repeat(None, N):
	(L, T) = input().strip().split(' ')
	(L, T) = [int(L), int(T)]
	if T == 0:
		luck += L
	else:
		important.append(L)
important.sort(reverse=True)
luck += sum(important[:K])
luck -= sum(important[K:])
print(luck)


(N, K) = list(map(int, input().split()))
unimp = []
imp = []
for i in range(N):
	(L, T) = list(map(int, input().split()))
	if T == 1:
		imp.append(L)
	else:
		unimp.append(L)
imp = list(reversed(sorted(imp)))
print(sum(unimp) + sum(imp[:K]) - sum(imp[K:]))


initial = input().split(' ')
soma = 0
menor = []
important = 0
for n in range(int(initial[0])):
	entrada = input().split(' ')
	soma += int(entrada[0])
	if int(entrada[1]) == 1:
		important += 1
		menor.append(int(entrada[0]))
menor.sort()
for i in range(important - int(initial[1])):
	soma -= menor[i] * 2
print(soma)


(n, K) = [int(x) for x in input().split()]
l = [0] * n
k = [0] * n
for i in range(n):
	(l[i], k[i]) = [int(x) for x in input().split()]
for j in range(1, n):
	temp = l[j]
	temp1 = k[j]
	r = j - 1
	while r >= 0 and l[r] > temp:
		l[r + 1] = l[r]
		k[r + 1] = k[r]
		r = r - 1
	l[r + 1] = temp
	k[r + 1] = temp1
sum = 0
c = 0
for z in range(n - 1, -1, -1):
	if c < K:
		if k[z] == 1:
			c = c + 1
			sum = sum + l[z]
		if k[z] == 0:
			sum = sum + l[z]
	elif c >= K:
		if k[z] == 1:
			c = c + 1
			sum = sum - l[z]
		if k[z] == 0:
			sum = sum + l[z]
print(sum)


(N, K) = tuple(map(int, input().strip().split(' ')))
ti = []
tu = []
su = 0
for i in range(N):
	(x, y) = tuple(map(int, input().strip().split(' ')))
	if y:
		ti.append(x)
	else:
		tu.append(x)
	su += x
ti = sorted(ti)
tu = sorted(tu)
if K >= len(ti):
	print(su)
else:
	off = len(ti) - K
	print(sum(ti[off:]) + sum(tu) - sum(ti[0:off]))


(n, k) = list(map(int, input().strip().split(' ')))
contests = []
losses = 0
luck_bal = 0
for i in range(n):
	(luck, imp) = list(map(int, input().strip().split(' ')))
	contests.append((luck, imp))
contests_sorted = sorted(contests, key=lambda x: x[0])[::-1]
for (luck, imp) in contests_sorted:
	if imp == 0:
		luck_bal += luck
	elif losses != k:
		losses += 1
		luck_bal += luck
	else:
		luck_bal -= luck
print(luck_bal)


stats = [int(thing) for thing in input().strip().split(' ')]
tests = []
luck = 0
count = stats[1]
for i in range(stats[0]):
	cocks = [int(thing) for thing in input().strip().split(' ')]
	if cocks[1] == 1:
		tests.append(cocks)
	else:
		luck += cocks[0]
tests.sort(reverse=True)
for i in range(len(tests)):
	if count != 0:
		luck += tests[i][0]
		count -= 1
	else:
		luck -= tests[i][0]
print(luck)


import queue as Q
q = Q.PriorityQueue()
(n, k) = input().split()
(n, k) = [int(n), int(k)]
totalLuck = 0
numImportant = 0
for _ in range(n):
	(l, t) = input().split()
	(l, t) = [int(l), int(t)]
	totalLuck += l
	if t == 1:
		q.put(l)
		numImportant += 1
while numImportant > k:
	l = q.get()
	totalLuck -= 2 * l
	numImportant -= 1
print(totalLuck)


import sys
(ntests, canLose) = [int(x) for x in sys.stdin.readline().split(' ')]
luck = 0
importants = []
for i in range(0, ntests):
	(value, important) = [int(x) for x in sys.stdin.readline().split(' ')]
	if important == 0:
		luck += value
	else:
		importants.append(value)
importants.sort()
hasToWin = len(importants) - canLose
k = 0
for imp in importants:
	if k < hasToWin:
		luck -= imp
		k += 1
	else:
		luck += imp
print(luck)


class Heap:

	def __init__(self, MAXHEAP):
		self.__MAXHEAP = bool(MAXHEAP)
		self.__heap = []
		self.__length = 0

	def __len__(self):
		return self.__length

	def __str__(self):
		items = [str(i) for i in self.__heap]
		return ' '.join(items)

	def clear(self):
		self.__heap = []

	def __siftdown(self, pos):
		while 2 * pos + 1 < self.__length:
			j = pos * 2 + 1
			rc = j + 1
			if self.__MAXHEAP:
				if rc < self.__length and self.__heap[j] < self.__heap[rc]:
					j = rc
				if self.__heap[pos] >= self.__heap[j]:
					return
				(self.__heap[pos], self.__heap[j]) = (self.__heap[j], self.__heap[pos])
			else:
				if rc < self.__length and self.__heap[j] > self.__heap[rc]:
					j = rc
				if self.__heap[pos] <= self.__heap[j]:
					return
				(self.__heap[pos], self.__heap[j]) = (self.__heap[j], self.__heap[pos])
			pos = j

	def enqueue(self, value):
		self.__heap.append(value)
		self.__length += 1
		for i in range(int(self.__length / 2) - 1, -1, -1):
			self.__siftdown(i)

	def dequeue(self):
		if self.__length == 0:
			return None
		value = self.__heap[0]
		self.__heap[0] = self.__heap[-1]
		self.__heap.pop()
		self.__length -= 1
		if self.__length != 0:
			self.__siftdown(0)
		return value

	def front(self):
		if self.__length == 0:
			return None
		return self.__heap[0]

	def isempty(self):
		return not bool(self.__length)
(N, K) = [int(i) for i in input().split()]
imp = []
not_imp = []
for n in range(N):
	(L, T) = [int(i) for i in input().split()]
	if T:
		imp.append(L)
	else:
		not_imp.append(L)
luck = 0
imp_heap = Heap(0)
not_imp_heap = Heap(0)
for elem in imp:
	imp_heap.enqueue(elem)
for elem in not_imp:
	not_imp_heap.enqueue(elem)
da_vincere = len(imp) - K
var = 0
for vincere in range(da_vincere):
	curr = imp_heap.dequeue()
	luck -= curr
while not imp_heap.isempty():
	luck += imp_heap.dequeue()
while not not_imp_heap.isempty():
	luck += not_imp_heap.dequeue()
print(luck)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
inp = list()
max_luck = 0
for i in range(n):
	(lck, imp) = list(map(int, input().strip().split(' ')))
	max_luck = max_luck + lck
	if imp == 1:
		inp += [lck]
inp.sort()
for i in range(len(inp) - k):
	max_luck -= 2 * inp[i]
print(max_luck)