410654: GYM104069 F Food Queue

New year, new cycle, new routine, new friends: joining a university such as USP brings lots of novelties.

The cafeteria is one of them!

The possibility of eating a full meal spending only R$2,00 is an unmissable opportunity. Therefore, almost everyone on the campus tries to eat in one of the four cafeterias: CENTRAL, FÍSICA, PREFEITURA and QUÍMICA.

Suppose there are $$$N$$$ people wanting to eat and the $$$i$$$-th person went to the cafeteria $$$b_i$$$ (C for CENTRAL, F for FISICA, P for PREFEITURA, and Q for QUIMICA) and takes $$$v_i$$$ minutes to eat. Since $$$N$$$ may be huge and some people can't eat fast (this problem's writer is one of them), the queue ends up being enormous! Besides that, each cafeteria can only handle one person at a time because of the pandemic.

Knowing that the cafeteria stays open for $$$T$$$ minutes, determine the maximum number of students that can eat. One does not need to follow the queue order. Each student must finish eating before the cafeteria closes.

The first line contains two integers: $$$N (1\leq N \leq 4 \cdot 10^5$$$) - the number of students - and $$$T (1\leq T \leq 10^9$$$) - the total time that cafeterias will stay open.

Then, $$$N$$$ lines follow. The $$$i$$$-th line contains a character $$$b_i$$$ - C, F, P or Q that represents the cafeteria - and an integer $$$v_i (1 \leq v_i \leq 10^9)$$$ which represents the time this person takes to eat.

Print one integer, the maximum number of students that can eat.

6 10
C 5
F 3
P 2
Q 4
C 1
C 6

5

1 1
C 3

0

4 10
C 6
C 3
C 4
C 5

2