Deadline-limited repairs: hints, no solution

A repair crew becomes available at minute start. Job i takes durations[i] minutes of uninterrupted work and must be finished no later than minute deadlines[i], meaning the finishing minute is at most the deadline. The crew works on one job at a time, with no breaks between jobs it chooses to do, and may take jobs in any order.

Some jobs may have to be declined. Return the greatest count of jobs the crew can complete so that every accepted job meets its own deadline. A job that cannot be finished on time even when done first is never accepted.

Examples

Input

durations = [4, 2, 3, 1], deadlines = [6, 3, 9, 4], start = 0

Output

3

Note

Do the jobs of length 2, 1 and 3 in that order; the job of length 4 would break its deadline.

Input

durations = [5], deadlines = [4], start = 0

Output

0

Note

The only job needs 5 minutes but its deadline is minute 4.

Constraints

• 0 <= number of jobs <= 100000
• 1 <= durations[i] <= 1000
• 1 <= deadlines[i] <= 1000000
• 0 <= start <= 1000000

Hint 1: a nudge

If you had already picked a set of jobs, in what order would you do them so that a deadline is least likely to be missed?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing