효율적으로 과제하기

면접 대비

시간 제한1초메모리 제한1024 MB

요약

과제를 골라 짧은 것부터 순서대로 수행할 때 얻을 수 있는 최대 점수와, 그 점수를 얻는 최소 시간을 구합니다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 정렬
정답자: 아직 제출이 없습니다

문제

요즘 시험 기간에도 밀린 과제 때문에 김한양은 매우 피곤하다. 중간고사를 망쳐서 재수강은 피하고 싶었고, 그래서 과제를 빨리 끝내고 기말고사 공부를 하고 싶었다.

재수강을 피하려면 과제에서 얻는 배점이 많을수록 좋다. 기말고사 공부에는 시간이 많이 필요하므로, 과제를 하는 데 드는 소요 시간이 적을수록 좋다. 김한양은 과제의 총 배점 합을 과제의 총 소요 시간 합보다 더 중요하게 생각한다. 따라서 가장 많은 배점을 얻을 때, 소요 시간이 가장 적은 순서대로 과제를 하는 것이 김한양에게 가장 효율적인 계획이다. 가장 많은 배점을 얻을 수만 있다면 모든 과제를 하지 않아도 괜찮다고 생각한다.

김한양은 이 효율적인 계획을 세우기 위해 과제를 일렬로 나열했다. 각 $i$ 번째 과제 $A_i$ 에 대해 과제를 해내는 데 필요한 소요 시간 $T_i$ (시간), 지금부터 마감 기한까지 남은 시간 $D_i$ (시간), 배점 $P_i$ 를 표로 정리했다.

지금 시작해서 과제 $A_i$ 를 하면 다음과 같이 배점을 받는다.

$D_i$ 이하의 시간 안에 끝내면 배점 $P_i$ 를 그대로 받는다.
$D_i$ 를 넘겼지만 $D_i+24$ 이하의 시간 안에 끝내면 지각 제출이므로, 배점의 절반을 내림한 $\lfloor P_i / 2\rfloor$ 를 받는다.
$D_i+24$ 를 넘기면 0점을 받는다.

집중력이 좋아서 과제 $A_i$ 는 정확히 $T_i$ 시간이 걸리지만, 과제 두 개 이상을 동시에 할 정도로 집중력이 좋지는 않다.

입력

첫 번째 줄에 과제의 개수 $N$ ( $1 \le N \le 20$ )이 주어진다. 이후 $N$ 개의 줄에 걸쳐 $i$ 번째 과제의 소요 시간 $T_i$ ( $1 \le T_i \le 10^3$ ), 남은 시간 $D_i$ ( $1 \le D_i \le N \times 10^3$ ), 배점 $P_i$ ( $1 \le P_i \le 10^6$ )가 양의 정수로 각각 주어진다. 모든 입력은 공백으로 구분된다.

출력

김한양이 효율적인 계획대로 행동할 때 얻을 수 있는 최대 배점과, 그 배점을 얻을 때 걸리는 최소 소요 시간(시간)을 공백으로 구분하여 출력한다.

예제3

예제 1

입력

예상 출력

20 48

예제 2
입력
```
3
120 120 15
30 60 5
30 60 10
```
예상 출력
```
15 60
```
예제 3
입력
```
2
100 10 100
200 20 200
```
예상 출력
```
0 0
```