금성 탐사 로버

면접 대비

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

요약

제한된 시간과 들어 올릴 수 있는 총 질량 안에서 고른 돌들의 가치 합이 최대가 되도록 돌을 선택한다.

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

문제

NASA가 화성 탐사 로버 스피릿과 오퍼튜니티를 화성으로 보낸 뒤, ASAN은 금성에서 어떤 귀중한 원자재를 얻을 수 있는지 알아내기 위해 금성 탐사 로버 그리디(Greedy)를 금성으로 보내기로 결정했다. 그리디의 임무는 금성 표면에서 돌을 수집하는 것이다.

그리디는 로켓에 실려 금성으로 이동한다. 로켓은 그리디를 커다란 컨테이너와 함께 표면에 내려놓은 뒤 금성 주위를 일곱 바퀴 돌고, 마지막에 탑재된 집게로 그리디와 컨테이너를 함께 회수한다.

착륙한 뒤 그리디는 IntelliSensor 기술로 반경 0.5마일 이내의 흥미로운 돌을 모두 탐색한다. 그 결과 각 돌마다 질량, 가치, 그리고 그 돌을 집어 컨테이너에 담는 데 걸리는 시간이 정확히 추정된 목록을 얻는다. 컨테이너는 모든 돌을 담을 수 있을 만큼 충분히 크지만, 로켓이 표면에서 들어 올릴 수 있는 질량에는 한계가 있다. 또한 로켓이 일곱 바퀴를 돌고 돌아오기 때문에 사용할 수 있는 시간에도 한계가 있다.

여러분의 임무는 담은 돌들의 가치 합이 최대가 되도록 어떤 돌을 골라 컨테이너에 담을지 결정하는 프로그램을 작성하는 것이다.

입력

첫 번째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

세 개의 양의 정수 $N$ , $T$ , $M$ 이 주어지는 줄. $0 < N \le 100$ 은 발견한 돌의 개수, $0 < T \le 100$ 은 로켓이 그리디와 컨테이너를 회수하러 돌아오기 전까지 사용할 수 있는 시간, $0 < M \le 100$ 은 로켓이 들어 올릴 수 있는 돌의 최대 질량이다.
이어서 $N$ 개의 줄이 주어지며, $i$ 번째 줄에는 세 개의 양의 정수 $t_i$ , $m_i$ , $v_i$ (모두 $10^6$ 이하)가 주어진다. 각각 $i$ 번 돌을 집는 데 필요한 시간, 추정 질량, 추정 가치를 나타낸다.

출력

각 테스트 케이스마다 해당 테스트 케이스에서 담을 수 있는 최대 가치 합을 한 줄에 하나의 정수로 출력한다.

예제4

예제 1

입력

예상 출력

100
19

예제 2
입력
```
1
1 5 5
5 5 50
```
예상 출력
```
50
```
예제 3
입력
```
1
1 100 1
1 2 100
```
예상 출력
```
0
```
예제 4
입력
```
1
1 1 100
2 1 100
```
예상 출력
```
0
```