A single venue receives n booking offers. Booking i occupies the half-open interval [start, end) and pays reward if accepted. Two bookings conflict if their intervals overlap over a stretch of positive length (bookings that only touch at an endpoint may both be accepted). Choose a set of pairwise non-conflicting bookings that maximizes the total reward, and report that maximum total.
Input format
Line 1: an integer n.
Next n lines: three integers start end reward (with start < end).
Output format
A single integer: the maximum total reward achievable.
Constraints
- 1 ≤ n ≤ 16
- 0 ≤ start < end ≤ 1000000
- 1 ≤ reward ≤ 1000000