Problem C
Chimchar Defense

In Piplup Nation, they are under attack by a horde of Chimchars. The battlefield can be represented by a line with $N$ areas labeled $1$ to $N$ from left to right.

There are $N$ Chimchars, with the $i^{\text{th}}$ Chimchar currently at area $i$ and having $H_i$ health remaining.

To defend the nation, there are $N$ Piplups, with the $i^{\text{th}}$ Piplup stationed at area $i$. Each Piplup can unleash a powerful Hydro Pump leftward, damaging Chimchars that are on its left (including its own area). Notably, the $i^{\text{th}}$ Piplup can fire a Hydro Pump that deals $D_i$ damage to all Chimchars in area $j \leq i$. However, each Chimchar only takes $\min (H, D_i)$ damage from the attack, where $H$ is the current health of the Chimchar.

Since Hydro Pump is a very powerful move, it has low PP, and each Piplup can only fire it once. Additionally, due to its low accuracy, the $i^{\text{th}}$ Piplup requires a certain number of X-Accuracy items, costing $C_i$, to successfully launch the attack.

As the commander of the Piplup army, your goal is to maximize the following value:

Input

The first line of input contains an single integer $N$ ($1 \leq N \leq 5000$), the number of areas.

The second line of input contains $N$ integers, $H_i$ ($1 \leq H_i\leq 5000$) the initial health of the $i^{\text{th}}$ Chimchars.

The third line of input contains $N$ integers, $D_i$ ($1 \leq D_i \leq 5000$) the attack damage of the $i^{\text{th}}$ Piplup.

The fourth line of input contains $N$ integers, $C_i$ ($0 \leq C_i \leq 10^{9}$) the attack cost of the $i^{\text{th}}$ Piplup.

Output

Output a single integer representing the maximum possible value of $(\text{Total damage to Chimchars}) - (\text{Total Cost})$.

Sample Explanation

If we choose to make Piplup $3$ and $5$ fire, the damage dealt to the chimchars would be $[6, 3, 2, 3, 1]$.

Thus, the total score would be $6 + 3 + 2 + 3 + 1 - 1 - 2 = 12$

5
6 3 2 5 1 
1 3 3 2 3 
1 5 1 10 2 

12