Problems
병호가 ‘L’ 백화점에서 ‘N’ 타이어를 팔려고 한다. 공장에서 출고한 타이어는 총 N종류 있다. 허나, 타이어들의 부피가 너무 크기 때문에 타이어를 운송할 때 타이어 안에 타이어를 끼우는 식으로 운송해야 한다.
병호는 정확히 한 개의 타이어 안에 여러 개의 타이어를 끼워서 타이어를 운송하려고 한다. 타이어들의 정보가 주어질 때, 병호가 팔 수 있는 타이어의 가격의 합의 최댓값을 구하여라.
Input
첫 번째 줄에는 출고한 타이어의 수 N(1 ≤ N ≤ 1,500)이 주어진다.
두 번째 줄부터 N개의 줄에는 각 타이어의 안지름 I, 바깥지름 O, 가격 P가 주어진다.
1 ≤ I < O ≤ 1,000,000,000, 1 ≤ P ≤ 1,000
Output
병호가 팔 수 있는 타이어의 가격의 합의 최댓값을 출력한다.
Example
5
2 6 9
1 2 7
3 5 5
8 12 5
5 7 3
21
Hint
Source
functionx
You must sign in to write code.