CSES - Aalto Competitive Programming 2024 - wk6 - Mon - Programming contest
  • 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