문제
블록 쌓기 한국 대표인 규찬이는 블록 쌓기 대회 챔피언이다. 그것도 3년 연속으로... 규찬이의 독주에 다른 나라 선수들은 규정을 바꾸자는 요청이 쇄도하여 블록 쌓기 대회 위원회에서는 올해는 규정을 바꾸기로 하였다.
바뀐 규정은 다음과 같다. 모든 블록은 직육면체이며 아랫면의 크기는 같은 모양이고 블록을 회전시킬 수 없다. K개의 다른 종류의 블록이 주어지는데 각 종류의 블록은 높이, 쌓을 수 있는 최대 고도(누적 높이), 개수 세 가지의 정보로 주어진다.
최대 고도라 함은 해당 블록은 그 고도 이하에서만 사용하여야 한다는 뜻이다.
이러한 블록으로 최대 높이로 쌓는 사람이 승자가 된다.
올해도 챔피언을 차지하고 싶은 규현이는 어떻게 해야 할까?
입력
첫 행에 블록의 가지 수 N ( 1 ≤ N ≤ 400)이 입력된다. 다음 행부터 N행에 걸쳐 블록의 정보가 입력되는데 블록의 높이 Hi ( 1 ≤ Hi ≤ 100), 블록의 최대 고도(누적 높이) Ai(1 ≤ Ai ≤ 40,000), 블록의 개수 Ci(1 ≤ Ci ≤10)가 공백으로 구분되어 주어진다.
출력
쌓을 수 있는 최대 높이를 출력하시오.
예제1
입력
3
7403
5238
2526
출력
48
힌트
출처
USACO 2005 March Gold