C. Chimchar Defense
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

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: $$$$$$(\text{Total damage dealt to Chimchars}) - (\text{Total cost})$$$$$$

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^{th}$$$ Chimchars.

The third line of input contains $$$N$$$ integers, $$$D_i$$$ ($$$1 \leq D_i \leq 5000$$$) the attack damage of the $$$i^{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^{th}$$$ Piplup.

Output

Output a single integer representing the maximum possible value of

$$$(\text{Total damage to Chimchars}) - (\text{Total Cost})$$$.

Example
Input
5
6 3 2 5 1
1 3 3 2 3
1 5 1 10 2
Output
12
Note

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$$$