Boss
Before the holidays, the Chief receives numerous invitations to festive meetings. To manage his schedule effectively, he has established a rule: each invitation must clearly specify the time interval [ a[i]; b[i] ] during which the meeting occurs. Furthermore, the Chief assigns an "importance" value c[i] to each meeting.
The Chief prefers to commit fully, meaning he either attends the entire meeting for its specified duration or not at all. There must be at least a minimal break between meetings he attends. Thus, the Chief can attend the j-th meeting (from the list of invitations) after the i-th one only if a[j] > b[i].
Write a program to help the Chief attend meetings with the highest possible total importance. If there are multiple sets of meetings with the same maximum total importance, choose the one with the lesser total duration of meetings.
Input
The program reads from the keyboard, starting with the first line containing the number of events N, where 2 ≤ N ≤ 98765. This is followed by N triplets(a[i], b[i], c[i]), each on a separate line. It is guaranteed that 0 ≤ a[i] < b[i] < 2^31 = 2147483648, all c[i] are natural numbers, and their sum does not exceed 10^9.
Output
The program should output to the screen the sum of importance and the sum of the duration of the selected meetings, separated by a space.