- Time limit: 2.00 s
- Memory limit: 512 MB
Uolevi is participating in a programming contest. There are n tasks that have to be solved in order of difficulty. Task i takes m_i minutes to solve and solving it t minutes after the contest started yields p_i - t points. If task i is harder than task j then m_i > m_j. Uolevi can choose to skip some or all of the tasks. Skipping a task takes no time. What is the maximum number of points Uolevi can achieve?
Input
The first line contains a single integer n. The second line contains n integers m_1,\,m_2,\ldots,\,m_n. The third line contains n integers p_1,\,p_2,\ldots,\,p_n.
Output
Print the maximum score Uolevi can get.
Constraints
- 1 \le n \le 10^5
- 1 \le m_i \le 10^6
- 1 \le p_i \le 10^6
- m_i < m_j if i < j
Example 1
Input:
5 1 2 3 4 5 10 19 19 12 14
Output:
41
Example 2
Input:
10 3 5 8 9 11 13 16 17 18 20 1 16 19 10 14 11 32 8 18 19
Output:
22