URI Online Judge | 2856

Cheese Bread Trip

By Dâmi Henrique, Inatel BR Brazil

Timelimit: 1

Adson, tired of staying at home, decided to take a motorcycle trip through Brazil. He prepared himself for weeks by writing down all the cities he would visit and all the points he would stop to eat on the road. Adson decided he would stop only at the cheese bread stalls of the famous company ScB (Stuffed Cheese Breads). 

Concerned not to spend too much on the cheese rolls, he noted only the places where they sold with the famous "Take X Cheese Breads and Pay Y Reais".

Adson defined R reais to spend on the cheese breads. Since gasoline is already too expensive, he needs your help to choose which stalls to stop to buy stuffed cheese breads so that you can buy as much as possible with a maximum of R reais.

The company ScB sells cheese bread with three different types of fillings: "Bacon, Cheddar or Guava". Adson thinks it is not a good idea to mix all three types on his trip and decided that he will buy cheese breads from at most two different types of filling.

Given the information on the number of N stalls along the trip, the amount of R reais that Adson owns, and the type of promotion each stall sells "Take X Cheese Breads and Pay Y Reais", your task is to help him by saying how much cheese bread can he buy without breaking the rule of buying a maximum of two different types. Consider that he can not buy more than once in the same tent.

Input

The first line contains two integers N and R, (1 ≤ N, R ≤ 1000), representing the quantity of stuffed cheese bread stalls and the amount of money(reais) Adson has for this purpose. Each of the next N lines will contain three integers X Z Y representing the information of the promotion of a tent: X cheese breads with stuffing Z for only Y reais. (1 ≤ X, Y ≤ 100) and Z = 'B', 'C', ou 'G', representing Bacon, Cheddar and Guava, respectively.

Output

Display a single integer, the largest quantity of cheese breads, of at most two different types, that Adson can buy without exceeding his budget.

Sample Input Sample Output

4 16
4 G 5
6 B 4
8 C 6
2 B 3

16

3 10
3 B 5
4 B 3
8 C 7

12