금성 탐사 로버

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$번 돌을 집는 데 필요한 시간, 추정 질량, 추정 가치를 나타낸다.

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