A single reactor processes tasks one at a time with no gaps, starting at time 0. Task i needs t[i] units of runtime, must finish no later than its deadline d[i], and is worth v[i] if completed. You may run any subset of tasks in any order you like; a chosen task's finish time (the running total of runtimes up to and including it) must be ≤ d[i].
Maximize the total value of the completed tasks, and output that maximum value.
Input format
Line 1: an integer n.
Next n lines: three integers t, d, v — runtime, deadline, and value of one task.
Output format
A single integer: the maximum total value of a schedulable subset of tasks.
Constraints
- 1 ≤ n ≤ 100000
- 1 ≤ t[i] ≤ 1000
- 1 ≤ d[i] ≤ 100000
- 1 ≤ v[i] ≤ 1000000000