CF926H Endless Roses Most Beautiful

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.

The first line contains two integers $ n $ and $ k $ ( $ 1

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.

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.