410654: GYM104069 F Food Queue

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Food Queuetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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.

Output

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

ExamplesInput
6 10
C 5
F 3
P 2
Q 4
C 1
C 6
Output
5
Input
1 1
C 3
Output
0
Input
4 10
C 6
C 3
C 4
C 5
Output
2

加入题单

上一题 下一题 算法标签: