시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB98403739.785%

문제

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

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

김한양은 이 효율적인 계획을 세우기 위해 모든 과제를 일렬로 나열했다. 그리고 각 $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)$가 양의 정수로 각각 주어진다. 모든 입력은 각각 공백을 사이로 해서 주어진다.

출력

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

예제 입력 1

4
6 48 10
18 24 5
12 24 5
30 24 10

예제 출력 1

20 48

가장 높은 배점을 받는 방법 중 하나는 (1번, 3번, 4번) 순서로 $20$점을 받는 경우이다. 이때 걸리는 최소 소요 시간은 $48$시간이다.

  • 1번 과제: 총 $6$시간을 소요하여 $10$점을 받는다.
  • 3번 과제: 총 $(6+12)$시간을 소요하여 $(10+5)$점을 받는다.
  • 4번 과제: 총 $(6+12+30)$시간을 소요하여 $(10+5+5)$점을 받는다. $5$점을 받는 이유는 지각이기 때문이다.

예제 입력 2

3
120 120 15
30 60 5
30 60 10

예제 출력 2

15 60

가장 높은 배점을 받는 방법 중 하나는 (2번, 3번) 순서로 $15$점을 받는 경우이다. 이때 걸리는 최소 소요 시간은 $60$시간이다. (1번)만 하는 경우도 최대 배점인 $15$점을 받을 수 있지만, 소요 시간이 $120$시간임을 유의해야 한다.

  • 2번 과제: 총 $30$시간을 소요하여 $5$점을 받는다.
  • 3번 과제: 총 $(30+30)$시간을 소요하여 $(5+10)$점을 받는다.

예제 입력 3

2
100 10 100
200 20 200

예제 출력 3

0 0

어떠한 경우도 배점을 얻을 수 없다. 따라서 최소 소요 시간도 $0$시간이다.