| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 78 | 42 | 30 | 68.182% |
When Blaster first started at Mines, he joined as many different extracurricular clubs as he could. He loves getting involved on campus, and he also loves that many clubs provide free pizza! Unfortunately, now he is in too many clubs, and some of the meetings overlap. Additionally, if he eats too much pizza, then he will be too full to do any more activities.
Blaster still wants to attend as many clubs as he can. Each club meeting is only one hour long, but some club meetings might be at the same time as each other. Different clubs give different amounts of pizza, so he needs to decide which meetings to go to in order to maximize the amount of clubs he goes to before getting full of pizza.
If Blaster chooses optimally, how many clubs will he be able to attend?
The first line of the input consists of two integers $n,c$ (1ドル \leq n \leq 10^3, 0 \leq c \leq 10^6$)---the number of clubs and the number of pizza slices Blaster can eat before being full, respectively.
The $i$-th line of the following $n$ lines contains two integers $t_i, p_i$ (0ドル \leq t_i < 24, 0 \leq p_i \leq 10^6$)---the hour of the day that the $i$-th club meets at and the number of pizza slices he will eat at the $i$-th meeting, respectively.
Output a single integer, the number of clubs that Blaster can attend.
3 6 18 3 19 2 20 1
3
In sample input 1, there are three clubs at 18:00, 19:00, and 20:00 that give 3ドル,ドル 2ドル,ドル and 1ドル$ slices of pizza, respectively. Blaster can eat 6ドル$ slices of pizza, so he can attend all three clubs.
3 4 18 3 19 2 20 1
2
4 12 17 3 17 5 19 4 19 10
2
In sample input 3, Blaster can either visit clubs 1ドル$ and 3ドル$ or visit clubs 2ドル$ and 3ドル$.
School > CS@Mines > CS@Mines HSPC 2025 K번