In this world, there are those who dread the life of working, and would much rather stay at home, living a life of a recluse, away from other people. Some dread social settings, and pessimistically view other people as superficial. Life is just another trash game to them, one that they have gradually grown tired of.

Little Nate, an eccentric shut-in who (by definition) stays at home most of the time, falls into the categories above. It is currently summer vacation for him, yet he remains cooped up at home, finding his own means to entertain himself. To him, summer vacation allows for a retreat from the hot weather outside, and he argues (to himself) that going out during summer vacation with friends only serves to expose oneself to the scorching heat of summer, and it hence defeats the purpose of summer vacation. For such a seemingly unmotivated person, he does find some things interesting, such as toys.

As Nate formulates the above arguments about summer vacation in his head while holding on to a stack of ~N~ blocks that he plans to sell, he recalls that he has no friends, and his mind wanders back to 3 months ago, when he enlisted your help for packing boxes in boxes to troll his non-existent friends. Nate is shocked at his heavy blunder and fruitless efforts, falls into a momentary state of depression, and as a result, lost his balance of the blocks he was holding onto, causing the blocks to all fall onto the ground. Luckily for Nate, the blocks fell in a straight line, and in the same order as how he stacked them previously.

Having a far-above-average memory, Nate is able to recall the exact widths and heights of each of the ~N~ blocks, and in the same order as they were on the ground. Every block has a square base and the ~i~th block from him (also ~i~th block from the left) has width ~W_i~ and value ~V_i~. Due to his prolonged time living as a shut-in, Nate has developed one of the seven deadly sins – Sloth. He only wishes to walk from left to right once, without turning back. Furthermore, Nate wishes to only stack blocks above those with a smaller base area than itself for better stability, as he does not wish to commit the same mistake of dropping the blocks, hence Nate may pick up a block ~j~ after block ~i~ (~j > i~) if and only if ~W_i > W_j~. Nate also wishes to attain a maximum total value of the blocks from stacking through this one time walk, to gain as much money as possible from selling the blocks he picks up. Nate has a computer beside him, and has typed the necessary information regarding the boxes. Despite his overwhelming brilliance, Nate lacks knowledge of computer programming, and so once again he enlists your help to find how to maximise the total value of the blocks he may pick up, while satisfying his other conditions.

Input Specification

The first line of input will contain an integer ~N~.

The following two lines will each contain ~N~ integers ~W_1, \dots, W_N~ and ~V_1, \dots, V_N~ respectively.

Output Specification

The output should contain exactly one line with one integer, the maximum value attainable if Nate were to pick up blocks strictly from left to right while satisfying his other conditions.

Constraints

For all subtasks:

~1 \le W_i \le 2^{30}~

~0 \le V_i \le 2^{30}~

Subtask 1 [17%]

~1 \le N \le 1000~

Subtask 2 [26%]

~1 \le N \le 1\,000\,000~

~V_i = V_j~ for all ~i~, ~j~.

Subtask 3 [57%]

~1 \le N \le 1\,000\,000~

Subtask 4 [0%]

Sample test cases.

Sample Input

6
5 3 7 1 4 6
4 2 4 1 6 9

Sample Output

13

Explanation for Sample Output

Nate picks up blocks 3, 6 (as ~7 > 6~) with a total value of ~4 + 9 = 13~, which is maximal.