시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 256 MB | 266 | 85 | 57 | 29.843% |
외계인들이 지구를 침략했다. (결국!) 스스로를 방어하지 않으면 죽는다! 아니면 동화되거나. 먹힐 수도 있다. 사실 잘 모르겠다.
외계인들은 다음과 같은 공격 패턴을 따른다. n명의 외계인이 있고, i번 외계인은 di 만큼 떨어진 곳에서 ai 시간에 나타난다. 이 외계인은 bi 시간에 당신을 공격할 것이다. 따라서 정확히 bi 시간 또는 그 이전에 처치해야 한다.
당신의 무기는 광자폭탄으로, 폭발력을 마음대로 조절할 수 있다. 만약 폭발력을 R로 설정하고 터뜨렸다면, 거리 R 이하의 모든 외계인이 즉사한다. 그리고 R 만큼의 연료를 소모한다.
공격당하지 않고 모든 외계인을 처치하는 데 필요한 최소 연료의 양을 구하여라.
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스마다 첫 줄에 외계인의 수 n (1 ≤ n ≤ 300)이 주어지고, 다음 n 줄에 ai, bi, di (1 ≤ ai < bi ≤ 10 000; 1 ≤ di ≤ 10 000)가 주어진다.
각 테스트 케이스마다, 한 줄에 모든 외계인을 처치하는 데 필요한 최소 연료의 양을 출력한다.
1 3 1 4 4 4 7 5 3 4 7
7