Аркадий решил купить букет роз своей подруге.
В цветочном магазине есть белые, оранжевые и красные розы, причём их суммарное количество равно n. Аркадий считает, что красные розы с белыми не сочетаются, поэтому не будет покупать букет, содержащий и красные, и белые розы. Кроме того, Аркадий не будет покупать одноцветный букет.
Всего Аркадий хочет купить ровно k роз. Для каждой розы известна её красота и цвет: красота i-й розы равна bi, а её цвет — ci («W» для белой розы, «O» для оранжевой розы и «R» для красной розы).
Определите максимально возможную суммарную красоту букета из k роз, удовлетворяющего условиям выше, либо сообщите, что собрать такой букет из роз, имеющихся в магазине, невозможно.
Выходные данные
Выведите максимально возможную суммарную красоту букета из k роз, который удовлетворяет описанным условиям. Если невозможно собрать ни одного такого букета, выведите -1.
Примечание
В первом примере Аркадий должен купить 3 розы. Он может, например, купить обе красные розы (их номера 1 и 2, а суммарная красота 7) и единственную оранжевую розу (её номер равен 3, а красота равна 4). Таким образом, суммарная красота букета будет равна 11.
Во втором примере Аркадий не сможет купить букет, так как все розы в магазине одноцветные.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
4 3 4 1 6
RROWW
|
11
|
|
2
|
5 2
10 20 14 20 11
RRRRR
|
-1
|
|
3
|
11 5
5 6 3 2 3 4 7 5 4 5 6
RWOORWORROW
|
28
|