Monotonic Daily Practice Optimization

Tianyi has planned a training schedule for n days. She wants to practice each day with a non‐decreasing number of time units. However, to protect her voice, on the i-th day she cannot practice more than t_i time units. Moreover, due to varying daily conditions (such as the weather), the benefit (or harm) per unit of practice time is different on each day; on day i practicing one unit of time increases her familiarity by w_i (note that w_i may be negative).

Your task is to determine the maximum total increase in her familiarity that can be achieved by choosing a valid non‐decreasing sequence of daily practice times x_1,x_2,...,x_n (with 0 ≤ x_i ≤ t_i for all i).

The mathematical formulation is:

[ \text{Maximize } \sum_{i=1}^n w_i,x_i, \quad \text{subject to } 0 \le x_1 \le x_2 \le \cdots \le x_n \le t_i\ (1\le i\le n). ]

Note: Because a day with negative w_i decreases the total familiarity when practicing, it might be best to practice as little as possible on those days, while on days with positive w_i you want to practice as much as possible. However, the non‐decreasing constraint forces some trade‐offs between consecutive days.

inputFormat

The input consists of three lines:

• The first line contains a single integer n (the number of days).
• The second line contains n space‐separated integers, where the i-th integer is t_i (the maximum practice units on day i).
• The third line contains n space‐separated integers, where the i-th integer is w_i (the benefit per practice unit on day i).

outputFormat

Output a single integer, which is the maximum total familiarity improvement (it may be negative if the optimal strategy leads to a decrease).

sample

2
5 100
100 -1

495