마트료시카 인형

면접 대비

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

요약

주어진 인형 중 가장 많은 인형을 골라 각 인형이 자신과 안에 든 인형 무게를 감당하도록 쌓습니다.

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

문제

마트료시카는 인형 안에 인형을 넣어 겹쳐 쌓는 러시아 인형이다. 인형마다 무게와 수납 능력이 다르다.

인형 하나 안에는 다른 인형 하나만 직접 넣고, 그 인형 안에 또 다른 인형을 넣는 식으로 하나의 사슬을 만든다. 수납 능력은 자기 무게를 포함한 값이다. 즉 사슬에 들어간 모든 인형에 대해 자기 무게와 그 안에 들어 있는 모든 인형의 무게를 더한 값이 그 인형의 수납 능력 이하여야 한다. 무게가 400g이고 수납 능력이 900g인 인형은 안에 최대 500g만큼의 인형을 담는다.

주어진 인형 중에서 골라 하나의 사슬로 겹쳐 넣을 때, 사슬에 들어가는 인형의 최대 개수를 구하라.

입력

각 줄에 인형 하나의 무게와 수납 능력이 하나 이상의 공백으로 구분되어 주어진다. 두 값의 단위는 모두 그램이다. 입력은 파일 끝까지 이어지고, 인형은 최대 6000개다. 무게는 100000 이하, 수납 능력은 20000000 이하의 양의 정수다.

출력

어떤 인형의 수납 능력도 넘기지 않으면서 하나의 사슬에 겹쳐 넣을 수 있는 인형의 최대 개수를 한 줄에 출력한다.

예제4

예제 1
입력
```
300 1000
1000 1200
200 600
100 101
```
예상 출력
```
3
```
예제 2
입력
```
5 5
```
예상 출력
```
1
```
예제 3
입력
```
10 5
```
예상 출력
```
0
```
예제 4
입력
```
1 100
1 100
1 100
1 100
1 100
```
예상 출력
```
5
```