USACO 2005 March Gold- 블록 쌓기 > 문제은행 : 정보올림피아드&알고리즘




2769 : 블록 쌓기

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
8 회   
시도횟수
45 회   

문제

블록 쌓기 한국 대표인 규찬이는 블록 쌓기 대회 챔피언이다. 그것도 3년 연속으로...

규찬이의 독주에 다른 나라 선수들은 규정을 바꾸자는 요청이 쇄도하여 블록 쌓기 대회 위원회에서는 올해는 규정을 바꾸기로 하였다.

 

바뀐 규정은 다음과 같다.

모든 블록은 직육면체이며 아랫면의 크기는 같은 모양이고 블록을 회전시킬 수 없다.

K개의 다른 종류의 블록이 주어지는데 각 종류의 블록은

높이, 쌓을 수 있는 최대 고도(누적 높이), 개수 세 가지의 정보로 주어진다. 

최대 고도라 함은 해당 블록은 그 고도 이하에서만 사용하여야 한다는 뜻이다. 

이러한 블록으로 최대 높이로 쌓는 사람이 승자가 된다.

 

올해도 챔피언을 차지하고 싶은 규현이는 어떻게 해야 할까?


입력형식

첫 행에 블록의 가지 수 N ( 1 ≤ N ≤ 400)이 입력된다. 다음 행부터 N행에 걸쳐 블록의 정보가 입력되는데 블록의 높이 Hi ( 1 ≤ Hi ≤ 100), 블록의 최대 고도(누적 높이) Ai(1 ≤ Ai ≤ 40,000), 블록의 개수 Ci(1 ≤ Ci ≤10)가 공백으로 구분되어 주어진다.


출력형식

쌓을 수 있는 최대 높이를 출력하시오.


입력 예

3
7 40 3
5 23 8
2 52 6

출력 예

48

Hint!

맨 아래층에 높이 5인 블록을 3개 쌓는다. 다음에 높이 7인 블록을 3개 쌓는다.

이어서 높이 2인 블록을 6개 쌓는다. 15 + 21 + 12 = 48로서 최대이다.




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP