Job Sequencing Problem
Given jobs with deadlines and profits, find the maximum profit achievable by scheduling jobs within their deadlines.
Input format
The first line contains N. The second line contains N deadlines (1-indexed). The third line contains N profits.
Output format
Print the maximum total profit scheduling at most one job per slot by deadline.
Constraints
- Values fit in a 64-bit signed integer
- Trailing whitespace and a trailing newline are ignored by the judge
Read from stdin, write to stdout. Sample cases below show the exact format.
Sample cases
Example 1
Input
4
4 1 3 2
20 10 40 30Expected output
100Example 2
Input
3
1 2 3
10 20 30Expected output
60