Club Pizza

시간 제한1초메모리 제한2048 MB

요약

각 동아리가 한 시간 동안 모이고 정해진 수의 피자 조각을 먹을 때, 같은 시간에 겹치지 않고 정해진 양을 넘지 않으면서 최대로 참석할 수 있는 동아리 수를 구한다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 정렬
정답자: 아직 제출이 없습니다

문제

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

예제 1
입력
```
3 6
18 3
19 2
20 1
```
예상 출력
```
3
```
예제 2
입력
```
3 4
18 3
19 2
20 1
```
예상 출력
```
2
```
예제 3
입력
```
4 12
17 3
17 5
19 4
19 10
```
예상 출력
```
2
```