Most Courses Before Their Deadlines

You have signed up for several online courses. courses[i] is a tuple (days, last_day): the course takes days full days, and it must be finished by the end of day last_day. You work on one course at a time, from start to finish, and your first free day is day 1.

So a course you start right after the end of day t is finished at the end of day t + days, which must be at most its last_day. You may skip courses. Write most_courses(courses) that returns the largest number of courses you can finish in time.

Examples

most_courses([(3, 4), (2, 3), (1, 6)])   # returns 2
most_courses([(1, 2), (2, 3), (1, 3)])   # returns 2
most_courses([(5, 4)])                   # returns 0
most_courses([(2, 5), (2, 5), (2, 5)])   # returns 2

In the first example you can take the 3-day course (finished at the end of day 3) and then the 1-day course (finished at the end of day 4). All three do not fit: the 2-day and 3-day courses need 5 days together, but one of them has to be finished by day 4.

Constraints

• 0 <= len(courses) <= 100,000
• 1 <= days, last_day <= 10^9