There are n jobs. Each job i takes exactly one unit of time to complete, has a deadline d_i (it must be scheduled into some integer time slot from 1 to d_i, inclusive), and earns a profit p_i if it is completed by its deadline. Only one job can occupy any given time slot, and each job is either scheduled whole (into a single slot at or before its deadline) or not scheduled at all (earning no profit). Choose which jobs to schedule, and into which slots, to maximize the total profit earned. Print that maximum total profit.
Input format
Line 1: an integer n.
Next n lines: two integers d_i p_i for job i.
Output format
A single integer: the maximum total profit achievable.
Constraints
- 1 <= n <= 15
- 1 <= d_i <= n
- 1 <= p_i <= 100