Doing Assignments Efficiently

Interview

Time limit1sMemory limit1024 MB

Summary

Pick a subset of assignments to do shortest-first, maximizing points (half for late work within 24 hours), then report the least total time that achieves that maximum.

Level: Medium5 of 10
Topics: Dynamic programming, Sorting
Solved: No attempts yet

Problem

Kim Hanyang is exhausted from the backlog of assignments, even during exam period. He already did badly on the midterm, and he does not want to retake the course, so he wants to finish the assignments quickly and study for the final exam.

To avoid a retake, more points from assignments are better. Studying for the final takes a lot of time, so less time spent on assignments is also better. Kim Hanyang cares more about the total points of the assignments than the total time they take. So, when he gets the most points, doing the assignments in order of shortest time is the most efficient plan for him. If he can get the most points, he is fine with skipping some assignments.

To make this plan, Kim Hanyang lined up all the assignments in a row. For each $i$ -th assignment $A_i$ , he recorded in a table the time $T_i$ (hours) needed to finish it, the time $D_i$ (hours) left from now until the deadline, and the points $P_i$ .

If he starts assignment $A_i$ now, he gets the following points.

If he finishes within $D_i$ hours, he gets the full $P_i$ points.
If he finishes after $D_i$ but within $D_i+24$ hours, it is a late submission, so he gets $\lfloor P_i / 2\rfloor$ points.
If he finishes after $D_i+24$ hours, he gets 0 points.

He is focused enough that each assignment takes exactly $T_i$ hours, but not focused enough to work on two assignments at once.

Input

The first line contains the number of assignments $N$ ( $1 \le N \le 20$ ). The next $N$ lines each contain three positive integers: the time $T_i$ ( $1 \le T_i \le 10^3$ ), the time left $D_i$ ( $1 \le D_i \le N \times 10^3$ ), and the points $P_i$ ( $1 \le P_i \le 10^6$ ) for the $i$ -th assignment. All values are separated by spaces.

Output

Print the maximum points Kim Hanyang can get by following the efficient plan, and the minimum time (hours) it takes to get those points, separated by a space.

Examples3

Example 1

Input

Expected output

20 48

Example 2
Input
```
3
120 120 15
30 60 5
30 60 10
```
Expected output
```
15 60
```
Example 3
Input
```
2
100 10 100
200 20 200
```
Expected output
```
0 0
```