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: interview

Starter code:

Solutions:
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=map(int,input().split())
cost=list(map(int,input().split()))
s=input()
#return
a=[]
b=[]
c=[]
#print(n,k,cost)
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 = 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))

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 = map(int, input().split())
a = list(map(int, input().split()))
s = input()
if k == 1:
    print(-1)
    return
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=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=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 = list(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
    else:
        if(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
    else:
        if(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)