Pillars

Pillars

There is a row of $N$ pillars numbered from $1$ to $N$. Pillar $i$ ($1 ≤ i ≤ N$) has a height of $H_i$. John is currently standing on pillar 1 and wishes to reach pillar $N$ through a sequence of jumps. John can jump straight from pillar $i$ to pillar $j$ if $i < j$ and no pillar standing between them is higher than either pillar $i$ or $j$. Pillar $k$ is between pillars $i$ and $j$ ($i < j$) if $i < k$ and $k < j$. Note that this means that if two pillars are adjacent ($j = i+1$) then there are no pillars between them and it is therefore always possible to jump from one to the other.

Whenever John jumps to a new pillar, he stops for a while to admire the view. The view from pillar $i$ has a view score of $V_i$, indicating how enjoyable the view is from that pillar. $V_i$ can be negative, meaning that the view is so awful it is unpleasant to look at. John wishes to find a sequence of jumps that starts at pillar $1$, ends at pillar $N$ and maximises the sum of the view scores of the pillars he visits (including pillars $1$ and $N$). What is the maximum sum of views he can achieve?

Input

The first line of input contains one integer: $N$. The second line of input contains $N$ integers: $H_1, H_2, …, H_N$. The third line of input contains $N$ integers: $V_1, V_2, …, V_N$.

Output

You should output one integer: the maximum sum of view scores John can achieve.

Constraints

• $2 ≤ N ≤ 200,000$
• $1 ≤ H_i ≤ 200,000$
• $-1,000,000,000 ≤ V_i ≤ 1,000,000,000$

Subtasks

• Subtask 1 (10%): $V_i > 0$ for all $1 ≤ i ≤ N$
• Subtask 2 (15%): $N ≤ 200$
• Subtask 3 (15%): $N ≤ 2,000$
• Subtask 4 (25%): $V_i < 0$ for all $1 ≤ i ≤ N$
• Subtask 5 (20%): $H_i ≠ H_j$ for all $1 ≤ i, j ≤ N, i ≠ j$
• Subtask 6 (15%): No further constraints

Example

In the example below, it is optimal to jump from pillar 1 to 6 by passing through pillars 4 and 5, for a total view score of 6.