← 返回题目列表

Codeforces · 926/H

H. 无尽的玫瑰最美

中文机器翻译题面 查看原题

阿尔卡迪决定给他的女朋友买玫瑰。

某花店有白玫瑰、橙玫瑰、红玫瑰,总数为n。阿尔卡迪认为红玫瑰和白玫瑰不适合在一起,所以他不会买同时含有红玫瑰和白玫瑰的花束。此外,阿尔卡迪不会购买所有玫瑰颜色相同的花束。

Arkady 想买正好 k 朵玫瑰。对于商店里的每一朵玫瑰,他都知道它的美丽和颜色:第 i 朵玫瑰的美丽是 bi,它的颜色是 ci(“W”代表白玫瑰,“O”代表橙色玫瑰,“R”代表红玫瑰)。

计算满足上述约束的 k 朵玫瑰花束的最大可能总美感,或确定不可能制作这样的花束。

输入

第一行包含两个整数 n 和 k (1 ≤ k ≤ n ≤ 200 000) — 节目中的玫瑰数量和 Arkady 想要购买的玫瑰数量。

第二行包含整数序列 b1, b2, ..., bn (1 ≤ bi ≤ 10 000),其中 bi 等于第 i 朵玫瑰的美丽程度。

第三行包含一个长度为n的字符串c,由大写英文字母“W”、“O”和“R”组成,其中ci表示第i朵玫瑰的颜色:“W”表示白色,“O”表示橙色,“R”表示红色。

输出

打印满足上述约束的 k 玫瑰花束的最大可能总美感。如果无法制作一束这样的花束,请打印 -1。

示例

输入 #1

5 3
4 3 4 1 6
RROWW

输出 #1

11

输入 #2

5 2
10 20 14 20 11
RRRRR

输出 #2

-1

输入 #3

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

输出 #3

28

注意

在第一个示例中,Arkady 想购买 3 朵玫瑰。例如,他可以同时购买红玫瑰(其指数为 1 和 2,其总美丽度为 7)和唯一的橙色玫瑰(其指数为 3,其美丽度为 4)。这样,花束的总美度就是11。

在第二个示例中,Arkady 无法购买花束,因为所有玫瑰的颜色都相同。