Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

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 ith block from him (also ith 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.


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

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

Sample Output


Explanation for Sample Output

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


There are no comments at the moment.