Most Profitable Jobs

A freelancer has been offered some jobs. Each job is a tuple (start, end, pay): it runs from time start to time end and pays pay. She can work on only one job at a time, but a job may start at the exact moment another one ends.

Write best_pay(jobs) that returns the most she can earn by choosing jobs that do not overlap.

Examples

best_pay([(1, 3, 50), (3, 5, 20), (2, 6, 100)])            # returns 100
best_pay([(1, 2, 5), (2, 3, 5), (3, 4, 5), (1, 4, 12)])    # returns 15
best_pay([])                                               # returns 0

In the second example the three short jobs fit one after another and pay 15 together, more than the single long job.

Constraints

• 0 <= len(jobs) <= 20000
• 0 <= start < end <= 10**9
• 1 <= pay <= 10000
• The jobs can come in any order.

Note

Python stops a program whose function calls go about 1,000 levels deep, so with this many jobs a recursive solution that goes one job deeper per call will fail: work through the jobs in a loop instead.