이타적인 개구리들

시간 제한3초메모리 제한512 MB

요약

깊이 d인 구덩이에서 점프력, 무게, 높이가 주어진 개구리들을 쌓아 올려 최대 몇 마리가 탈출할 수 있는지 구합니다.

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

문제

넓은 웅덩이 바닥에 개구리 여러 마리가 떨어졌다. 이들이 빠져나갈 방법은 뛰어오르는 것뿐이다. 각 개구리 i는 세 값 $(l_i, w_i, h_i)$ 로 표현된다. 여기서 $l_i$ 는 도약 능력, $w_i$ 는 무게, $h_i$ 는 키다. 도약 능력은 그 개구리가 뛰어오를 수 있는 높이다. 도약 능력이 웅덩이 깊이보다 严格히 큰 개구리는 혼자서 탈출할 수 있다.

이 개구리들은 이타적이다. 자기만 살아남고 도약 능력이 부족한 개구리를 남겨 두지 않는다. 힘을 합쳐 최대한 많은 개구리를 웅덩이 밖으로 내보내려 한다.

개구리 A가 뛰기 전에 개구리 B의 등에 올라타면 A가 탈출할 가능성이 높아진다. $h_B + l_A$ 가 웅덩이 깊이보다 严格히 크면 A는 탈출할 수 있다.

B가 A를 업은 채 개구리 C의 등에 올라타면 A의 처지는 한층 나아진다. $h_C + h_B + l_A$ 가 웅덩이 깊이보다 严格히 크면 A는 탈출할 수 있다.

개구리들은 이런 방식으로 더 높은 더미를 쌓을 수 있다. 제약은 하나뿐이다. 한 개구리가 업고 있는 다른 개구리들의 무게 합은 자기 무게보다 작아야 한다. 더미가 누군가의 탈출에 쓰이면, 더미를 이루던 개구리들은 다시 웅덩이 바닥으로 뛰어내린다. 그다음 이들은 구성이 다른 새 더미를 만들 수 있다.

개구리들이 협력해서 탈출하는 개구리 수를 최대화할 때, 최대 몇 마리가 탈출할 수 있는지 구하라.

입력

첫 줄에 정수 $n$ 과 $d$ 가 주어진다 ( $1 \le n \le 10^5$ , $1 \le d \le 10^8$ ). $n$ 은 개구리 수이고, $d$ 는 웅덩이 깊이(µm)다. 이어지는 $n$ 줄에는 정수 $l$ , $w$ , $h$ 가 한 줄에 하나씩 주어진다 ( $1 \le l, w, h \le 10^8$ ). 각각 도약 능력 $l$ µm, 무게 $w$ µg, 키 $h$ µm인 개구리를 나타낸다. 모든 개구리 무게의 합은 $10^8$ µg 이하다.

출력

탈출할 수 있는 개구리의 최대 수를 출력한다.

예제2

예제 1
입력
```
3 19
15 5 3
12 4 4
20 10 5
```
예상 출력
```
3
```
예제 2
입력
```
3 19
14 5 3
12 4 4
20 10 5
```
예상 출력
```
2
```