Arkady decided to buy roses for his girlfriend.

A flower shop has white, orange and red roses, and the total amount of them is n. Arkady thinks that red roses are not good together with white roses, so he won't buy a bouquet containing both red and white roses. Also, Arkady won't buy a bouquet where all roses have the same color. 

Arkady wants to buy exactly k roses. For each rose in the shop he knows its beauty and color: the beauty of the i-th rose is b_{i}, and its color is c_{i} ('W' for a white rose, 'O' for an orange rose and 'R' for a red rose). 

Compute the maximum possible total beauty of a bouquet of k roses satisfying the constraints above or determine that it is not possible to make such a bouquet.


-----Input-----

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 200 000) — the number of roses in the show and the number of roses Arkady wants to buy.

The second line contains a sequence of integers b_1, b_2, ..., b_{n} (1 ≤ b_{i} ≤ 10 000), where b_{i} equals the beauty of the i-th rose.

The third line contains a string c of length n, consisting of uppercase English letters 'W', 'O' and 'R', where c_{i} denotes the color of the i-th rose: 'W' denotes white, 'O'  — orange, 'R' — red.


-----Output-----

Print the maximum possible total beauty of a bouquet of k roses that satisfies the constraints above. If it is not possible to make a single such bouquet, print -1.


-----Examples-----
Input
5 3
4 3 4 1 6
RROWW

Output
11

Input
5 2
10 20 14 20 11
RRRRR

Output
-1

Input
11 5
5 6 3 2 3 4 7 5 4 5 6
RWOORWORROW

Output
28



-----Note-----

In the first example Arkady wants to buy 3 roses. He can, for example, buy both red roses (their indices are 1 and 2, and their total beauty is 7) and the only orange rose (its index is 3, its beauty is 4). This way the total beauty of the bouquet is 11. 

In the second example Arkady can not buy a bouquet because all roses have the same color.

Difficulty: HARD

Starter code:

Solutions:
(n, k) = list(map(int, input().split()))
b = list(map(int, input().split()))
s = input()
a = []
if k == 1:
	print(-1)
	return
for i in range(n):
	a.append((b[i], s[i]))
a.sort(reverse=True)
i = 0
j = 0
m1 = 0
q1 = False
q2 = False
while i != k:
	if a[j][1] != 'R':
		m1 += a[j][0]
		g = j + 0
		if a[j][1] == 'W':
			q1 = True
		else:
			q2 = True
		i += 1
	j += 1
	if j == n and i != k:
		m1 = 0
		break
else:
	if not (q1 and q2):
		m1 -= a[g][0]
		for i in range(g + 1, n):
			if q1 and a[i][1] == 'O' or (q2 and a[i][1] == 'W'):
				m1 += a[i][0]
				break
		else:
			m1 = 0
i = 0
j = 0
m2 = 0
q1 = False
q2 = False
while i != k:
	if a[j][1] != 'W':
		m2 += a[j][0]
		g = j + 0
		if a[j][1] == 'R':
			q1 = True
		else:
			q2 = True
		i += 1
	j += 1
	if j == n and i != k:
		m2 = 0
		break
else:
	if not (q1 and q2):
		m2 -= a[g][0]
		for i in range(g + 1, n):
			if q1 and a[i][1] == 'O' or (q2 and a[i][1] == 'R'):
				m2 += a[i][0]
				break
		else:
			m2 = 0
if m1 or m2:
	print(max(m1, m2))
else:
	print(-1)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
s = input()
if k == 1:
	print(-1)
	exit(0)
have = [[] for i in range(3)]
for i in range(n):
	if s[i] == 'R':
		have[0].append(a[i])
	elif s[i] == 'O':
		have[1].append(a[i])
	else:
		have[2].append(a[i])
for i in range(3):
	have[i].sort(reverse=True)
ans1 = 0
p = 0
q = 0
was = [0, 0]
for i in range(k - 1):
	if p == len(have[0]) and q == len(have[1]):
		ans1 = -1
		break
	if p == len(have[0]):
		ans1 += have[1][q]
		q += 1
		was[1] = 1
	elif q == len(have[1]):
		ans1 += have[0][p]
		p += 1
		was[0] = 1
	elif have[0][p] > have[1][q]:
		ans1 += have[0][p]
		p += 1
		was[0] = 1
	else:
		ans1 += have[1][q]
		q += 1
		was[1] = 1
if ans1 != -1 and sum(was) == 2:
	if p == len(have[0]) and q == len(have[1]):
		ans = -1
	elif p == len(have[0]):
		ans1 += have[1][q]
	elif q == len(have[1]):
		ans1 += have[0][p]
	else:
		ans1 += max(have[0][p], have[1][q])
if ans1 != -1 and was[0] == 0:
	if p != len(have[0]):
		ans1 += have[0][p]
	else:
		ans1 = -1
if ans1 != -1 and was[1] == 0:
	if q != len(have[1]):
		ans1 += have[1][q]
	else:
		ans1 = -1
ans2 = 0
p = 0
q = 0
was = [0, 0]
for i in range(k - 1):
	if p == len(have[2]) and q == len(have[1]):
		ans2 = -1
		break
	if p == len(have[2]):
		ans2 += have[1][q]
		q += 1
		was[1] = 1
	elif q == len(have[1]):
		ans2 += have[2][p]
		p += 1
		was[0] = 1
	elif have[2][p] > have[1][q]:
		ans2 += have[2][p]
		p += 1
		was[0] = 1
	else:
		ans2 += have[1][q]
		q += 1
		was[1] = 1
if ans2 != -1 and sum(was) == 2:
	if p == len(have[2]) and q == len(have[1]):
		ans = -1
	elif p == len(have[2]):
		ans2 += have[1][q]
	elif q == len(have[1]):
		ans2 += have[2][p]
	else:
		ans2 += max(have[2][p], have[1][q])
if ans2 != -1 and was[0] == 0:
	if p != len(have[2]):
		ans2 += have[2][p]
	else:
		ans2 = -1
if ans2 != -1 and was[1] == 0:
	if q != len(have[1]):
		ans2 += have[1][q]
	else:
		ans2 = -1
print(max(ans1, ans2))


(n, k) = map(int, input().split())
cost = list(map(int, input().split()))
s = input()
a = []
b = []
c = []
kek1 = 0
kek2 = 0
kek3 = 0
for i in range(n):
	if s[i] == chr(ord('W')):
		kek1 += 1
		a.append(cost[i])
	if s[i] == chr(ord('O')):
		kek2 += 1
		b.append(cost[i])
	if s[i] == chr(ord('R')):
		kek3 += 1
		c.append(cost[i])
a = sorted(a)
a = list(reversed(a))
b = sorted(b)
b = list(reversed(b))
c = sorted(c)
c = list(reversed(c))
pref_a = []
pref_b = []
pref_c = []
if kek1 != 0:
	pref_a.append(a[0])
	for i in range(1, len(a)):
		pref_a.append(pref_a[len(pref_a) - 1] + a[i])
if kek2 != 0:
	pref_b.append(b[0])
	for i in range(1, len(b)):
		pref_b.append(pref_b[len(pref_b) - 1] + b[i])
if kek3 != 0:
	pref_c.append(c[0])
	for i in range(1, len(c)):
		pref_c.append(pref_c[len(pref_c) - 1] + c[i])
inf = 10 ** 20
ans = -inf
for i in range(0, min(k - 1, kek2)):
	cur = pref_b[i]
	left_k = k - (i + 1)
	res_a = -inf
	res_c = -inf
	if kek1:
		if kek1 >= left_k:
			res_a = pref_a[left_k - 1]
	if kek3:
		if kek3 >= left_k:
			res_c = pref_c[left_k - 1]
	cur += max(res_a, res_c)
	ans = max(ans, cur)
if ans < -10 ** 18:
	ans = -1
print(ans)


(n, k) = map(int, input().split())
a = [int(i) for i in input().split()]
w = []
r = []
o = []
s = input()
for i in range(n):
	if s[i] == 'O':
		o.append(a[i])
	if s[i] == 'R':
		r.append(a[i])
	if s[i] == 'W':
		w.append(a[i])
(o.sort(), w.sort(), r.sort())
w = w[::-1]
o = o[::-1]
r = r[::-1]
ans = -1
i = 0
j = 0
cntf = 0
cnts = 0
nw = 0
while cntf + cnts < k and (i < len(w) or j < len(o)):
	if i >= len(w):
		nw += o[j]
		j += 1
		cnts += 1
	elif j >= len(o):
		nw += w[i]
		i += 1
		cntf += 1
	elif w[i] > o[j]:
		nw += w[i]
		i += 1
		cntf += 1
	else:
		nw += o[j]
		j += 1
		cnts += 1
	if cntf + cnts == k - 1:
		if cntf == 0 and len(w) != 0:
			nw += w[i]
			cntf += 1
		elif cnts == 0 and len(o) != 0:
			nw += o[j]
			cnts += 1
if cntf + cnts == k and cntf != 0 and (cnts != 0):
	ans = max(ans, nw)
i = 0
j = 0
cntf = 0
cnts = 0
nw = 0
while cntf + cnts < k and (i < len(r) or j < len(o)):
	if i >= len(r):
		nw += o[j]
		j += 1
		cnts += 1
	elif j >= len(o):
		nw += r[i]
		i += 1
		cntf += 1
	elif r[i] > o[j]:
		nw += r[i]
		i += 1
		cntf += 1
	else:
		nw += o[j]
		j += 1
		cnts += 1
	if cntf + cnts == k - 1:
		if cntf == 0 and len(r) != 0:
			nw += r[i]
			cntf += 1
		elif cnts == 0 and len(o) != 0:
			nw += o[j]
			cnts += 1
if cntf + cnts == k and cntf != 0 and (cnts != 0):
	ans = max(ans, nw)
print(ans)


(n, k) = [int(x) for x in input().strip().split(' ')]
b = [int(x) for x in input().strip().split(' ')]
c = input().strip()
w = sorted([b[i] for i in range(len(b)) if c[i] == 'W'])
o = sorted([b[i] for i in range(len(b)) if c[i] == 'O'])
r = sorted([b[i] for i in range(len(b)) if c[i] == 'R'])
if k == 1 or len(o) == 0 or (len(w) == 0 and len(r) == 0):
	print(-1)
	return
max_wo = -1
if len(w) > 0 and len(w) + len(o) >= k:
	wo = sorted(w[:-1] + o[:-1])
	max_wo = w[-1] + o[-1]
	if k > 2:
		max_wo += sum(wo[-(k - 2):])
max_ro = -1
if len(r) > 0 and len(r) + len(o) >= k:
	ro = sorted(r[:-1] + o[:-1])
	max_ro = r[-1] + o[-1]
	if k > 2:
		max_ro += sum(ro[-(k - 2):])
ans = max(max_wo, max_ro)
print(ans)


(n, k) = list(map(int, input().split()))
b = list(map(int, input().split()))
SSSSSSSSSS = input()
INF = 1000 * 1000 * 1000 + 123
RRRR = []
WWWWWWW = []
OOOOOOOOO = []
for i in range(n):
	if SSSSSSSSSS[i] == 'R':
		RRRR.append(b[i])
	elif SSSSSSSSSS[i] == 'W':
		WWWWWWW.append(b[i])
	else:
		OOOOOOOOO.append(b[i])
WWWWWWW.sort()
RRRR.sort()
WWWWWWW.reverse()
RRRR.reverse()
OOOOOOOOO.sort()
OOOOOOOOO.reverse()
if k == 1:
	print(-1)
	return

def cccmcmc(A, B):
	qanakA = len(A)
	qanakB = len(B)
	pA = [0 for i in range(qanakA)]
	pB = [0 for i in range(qanakB)]
	pB[0] = B[0]
	pA[0] = A[0]
	for i in range(1, qanakA):
		pA[i] = pA[i - 1] + A[i]
	for i in range(1, qanakB):
		pB[i] = pB[i - 1] + B[i]
	res = -1
	for i in range(1, min(qanakA + 1, k)):
		aic = pA[i - 1]
		bepetk = k - i
		if bepetk <= 0 or bepetk > qanakB:
			continue
		bic = pB[bepetk - 1]
		res = max(res, aic + bic)
	return res
res = -1
if len(WWWWWWW) > 0 and len(OOOOOOOOO) > 0:
	res = max(res, cccmcmc(WWWWWWW, OOOOOOOOO))
if len(RRRR) > 0 and len(OOOOOOOOO) > 0:
	res = max(res, cccmcmc(RRRR, OOOOOOOOO))
print(res)


(n, k) = list(map(int, input().split()))
b = list(map(int, input().split()))
s = input()
r = []
w = []
o = []
for i in range(n):
	if s[i] == 'W':
		w.append(b[i])
	elif s[i] == 'O':
		o.append(b[i])
	else:
		r.append(b[i])
if k == 1:
	print(-1)
	raise SystemExit
r = sorted(r)
w = sorted(w)
o = sorted(o)
r = r[::-1]
w = w[::-1]
o = o[::-1]
s1 = 0
s2 = 0
if len(o) != 0 and len(w) != 0 and (len(o) + len(w) >= k):
	s1 += w[0] + o[0]
	j = 2
	i = 1
	e = 1
	while j < k:
		if i == len(o) or (e < len(w) and w[e] > o[i]):
			s1 += w[e]
			e += 1
		else:
			s1 += o[i]
			i += 1
		j += 1
if len(o) != 0 and len(r) != 0 and (len(o) + len(r) >= k):
	s2 += o[0] + r[0]
	j = 2
	i = 1
	e = 1
	while j < k:
		if i == len(o) or (e < len(r) and r[e] > o[i]):
			s2 += r[e]
			e += 1
		else:
			s2 += o[i]
			i += 1
		j += 1
if max(s1, s2) == 0:
	print(-1)
else:
	print(max(s1, s2))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = input()
r = []
o = []
w = []
for i in range(n):
	if b[i] == 'R':
		r.append(a[i])
	elif b[i] == 'O':
		o.append(a[i])
	else:
		w.append(a[i])
r.sort()
o.sort()
w.sort()
r.reverse()
o.reverse()
w.reverse()
if k == 1 or (len(r) * len(o) == 0 and len(o) * len(w) == 0):
	print('-1')
else:
	r1 = 0
	o1 = 0
	ans1 = 0
	o2 = 0
	w2 = 0
	ans2 = 0
	if len(r) + len(o) >= k and len(r) * len(o) != 0:
		r1 = 1
		o1 = 1
		ans1 = r[0] + o[0]
		while r1 + o1 < k:
			if o1 >= len(o) or (r1 < len(r) and r[r1] > o[o1]):
				ans1 += r[r1]
				r1 += 1
			else:
				ans1 += o[o1]
				o1 += 1
	if len(o) + len(w) >= k and len(o) * len(w) != 0:
		o2 = 1
		w2 = 1
		ans2 = o[0] + w[0]
		while o2 + w2 < k:
			if o2 >= len(o) or (w2 < len(w) and w[w2] > o[o2]):
				ans2 += w[w2]
				w2 += 1
			else:
				ans2 += o[o2]
				o2 += 1
	if max(ans1, ans2) == 0:
		print('-1')
	else:
		print(max(ans1, ans2))