효율적으로 과제하기

요즘 시험 기간에도 밀려 있는 과제 때문에 김한양은 매우 피곤하다. 안 그래도 중간고사를 망쳤고, 재수강은 하고 싶지 않았기에 과제를 빨리 마치고 기말고사 공부를 하고 싶었다.

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

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

그다음, 김한양이 지금 시간을 기준으로 과제 $A_i$를 함으로서 받을 수 있는 배점은 다음과 같다고 가정했다.

1. $D_i$ 이하의 시간 안에 과제를 했을 경우 그 과제의 배점 $P_i$를 그대로 받는다.
2. $D_i$를 넘겼지만, 그다음 날 전까지인 $D_i+24$ 이하의 시간 안에 과제를 했을 경우, 지각 제출이므로 배점의 절반을 내림한 $\lfloor P_i / 2\rfloor$를 받는다.
3. $D_i+24$를 넘긴 경우에는 어떠한 배점도 받지 못한다. 즉, $0$점을 받는다.

그러나 과제를 하는 방법의 수가 너무 많아서 김한양이 효율적인 계획을 세우는 데 어려움을 겪고 있다. 김한양은 집중력이 좋아서 과제 $A_i$를 하는 데 정확히 $T_i$의 시간이 걸리지만, $2$개 이상의 과제를 동시에 할 수 있을 정도로 집중력이 좋지는 않다. 김한양이 무사히 재수강을 피할 수 있도록 도와주자!

첫 번째 줄에 과제의 개수를 나타내는 정수 $N(1≤N≤20)$이 주어진다.

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

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