English · Original
Chinese · Translation
Formal · Original
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_.
[samples]
## 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.
Arkady 决定为他的女朋友买玫瑰。
一家花店有白色、橙色和红色的玫瑰，总数为 $n$。Arkady 认为红色玫瑰与白色玫瑰不搭配，因此他不会购买同时包含红色和白色玫瑰的花束。此外，Arkady 也不会购买所有玫瑰颜色都相同的花束。
Arkady 想要恰好购买 $k$ 朵玫瑰。对于花店中的每朵玫瑰，他知道它的美丽值和颜色：第 $i$ 朵玫瑰的美丽值为 $b_i$，颜色为 $c_i$（'_W_' 表示白色玫瑰，'_O_' 表示橙色玫瑰，'_R_' 表示红色玫瑰）。
请计算满足上述约束条件的 $k$ 朵玫瑰花束的最大可能总美丽值，或确定无法构造这样的花束。
第一行包含两个整数 $n$ 和 $k$（$1 ≤ k ≤ n ≤ 200 000$）——花店中玫瑰的数量和 Arkady 想要购买的玫瑰数量。
第二行包含一个整数序列 $b_1, b_2, ..., b_n$（$1 ≤ b_i ≤ 10 000$），其中 $b_i$ 表示第 $i$ 朵玫瑰的美丽值。
第三行包含一个长度为 $n$ 的字符串 $c$，由大写英文字母 '_W_'、'_O_' 和 '_R_' 组成，其中 $c_i$ 表示第 $i$ 朵玫瑰的颜色：'_W_' 表示白色，'_O_' 表示橙色，'_R_' 表示红色。
请输出满足上述约束条件的 $k$ 朵玫瑰花束的最大可能总美丽值。如果无法构造这样的花束，请输出 _-1_。
在第一个例子中，Arkady 想要购买 $3$ 朵玫瑰。例如，他可以购买两朵红色玫瑰（它们的下标是 $1$ 和 $2$，总美丽值为 $7$）和唯一的橙色玫瑰（下标是 $3$，美丽值为 $4$）。这样花束的总美丽值为 $11$。
在第二个例子中，Arkady 无法购买花束，因为所有玫瑰颜色都相同。
## Input
第一行包含两个整数 $n$ 和 $k$（$1 ≤ k ≤ n ≤ 200 000$）——花店中玫瑰的数量和 Arkady 想要购买的玫瑰数量。第二行包含一个整数序列 $b_1, b_2, ..., b_n$（$1 ≤ b_i ≤ 10 000$），其中 $b_i$ 表示第 $i$ 朵玫瑰的美丽值。第三行包含一个长度为 $n$ 的字符串 $c$，由大写英文字母 '_W_'、'_O_' 和 '_R_' 组成，其中 $c_i$ 表示第 $i$ 朵玫瑰的颜色：'_W_' 表示白色，'_O_' 表示橙色，'_R_' 表示红色。
## Output
请输出满足上述约束条件的 $k$ 朵玫瑰花束的最大可能总美丽值。如果无法构造这样的花束，请输出 _-1_。
[samples]
## Note
在第一个例子中，Arkady 想要购买 $3$ 朵玫瑰。例如，他可以购买两朵红色玫瑰（它们的下标是 $1$ 和 $2$，总美丽值为 $7$）和唯一的橙色玫瑰（下标是 $3$，美丽值为 $4$）。这样花束的总美丽值为 $11$。在第二个例子中，Arkady 无法购买花束，因为所有玫瑰颜色都相同。
**Definitions**
Let $ n, k \in \mathbb{Z}^+ $ with $ 1 \leq k \leq n \leq 200{,}000 $.
Let $ B = (b_1, b_2, \dots, b_n) $ be a sequence of rose beauties, where $ b_i \in \mathbb{Z}^+ $ and $ 1 \leq b_i \leq 10{,}000 $.
Let $ C = c_1 c_2 \dots c_n $ be a string over $ \{ \text{W}, \text{O}, \text{R} \} $, where $ c_i $ denotes the color of the $ i $-th rose.
Define three multisets:
- $ W = \{ b_i \mid c_i = \text{W} \} $, the beauties of white roses,
- $ O = \{ b_i \mid c_i = \text{O} \} $, the beauties of orange roses,
- $ R = \{ b_i \mid c_i = \text{R} \} $, the beauties of red roses.
**Constraints**
A valid bouquet $ S \subseteq \{1, \dots, n\} $ with $ |S| = k $ must satisfy:
1. $ S $ does **not** contain both a white and a red rose (i.e., $ S \cap W = \emptyset $ or $ S \cap R = \emptyset $),
2. $ S $ is **not** monochromatic (i.e., $ S \not\subseteq W $, $ S \not\subseteq O $, $ S \not\subseteq R $).
**Objective**
Maximize $ \sum_{i \in S} b_i $ over all valid bouquets $ S $.
If no such bouquet exists, output $ -1 $.
API Response (JSON)
{
"problem": {
"name": "H. Endless Roses Most Beautiful",
"description": {
"content": "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",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF953H"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Arkady decided to buy roses for his girlfriend.\n\nA 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...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Arkady 决定为他的女朋友买玫瑰。\n\n一家花店有白色、橙色和红色的玫瑰，总数为 $n$。Arkady 认为红色玫瑰与白色玫瑰不搭配，因此他不会购买同时包含红色和白色玫瑰的花束。此外，Arkady 也不会购买所有玫瑰颜色都相同的花束。\n\nArkady 想要恰好购买 $k$ 朵玫瑰。对于花店中的每朵玫瑰，他知道它的美丽值和颜色：第 $i$ 朵玫瑰的美丽值为 $b_i$，颜色为 $c_i$（'_W_...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq k \\leq n \\leq 200{,}000 $. \nLet $ B = (b_1, b_2, \\dots, b_n) $ be a sequence of rose beauties, where $ b_i \\in \\mathbb{Z}^+ $ and $ 1 \\le...",
"is_translate": false,
"language": "Formal"
}
]
}