CengTube is a video sharing platform developed by the junior METU CENG students. Being confident that this platform will be the next biggest social media platform in a few months, Kolsuz and Yiit had set up a CengTube channel, and it is already one of the most-followed channels.

To increase their number of followers, Kolsuz and Yiit came up with a new challenge idea: Parkour and Sodas!
For this challenge, Yiit will be drinking from soda cans and crushing empty cans while doing parkour for coolness points.
Among the \(\mathbf{n}\) soda cans, upon picking up the \(\mathbf{i^{th}}\) soda can,
Yiit will empty the can by drinking it, and doing so will award him with \(\mathbf{d_i}\) *coolness points*.
However, drinking soda way too fast makes carbonation burn Yiit's throat,
resulting in him not being able to drink the next \(\mathbf{dp_i}\) soda cans.

To gain even more *coolness points*, Yiit can crush an empty can after drinking it. Doing so will award him additional \(\mathbf{c_i}\) *coolness points*,
but doing so will make his head hurt, and he won't be able to pickup the next \(\mathbf{cp_i}\) cans in addition to the \(\mathbf{dp_i}\) cans.

Yiit needs to finish the parkour as quickly as possible. For that reason, he shouldn't carry soda cans around. After picking up a soda can, he must immediately empty that can and crush the can if he chooses to. Also, he can only go forward in the parkour: if he walks past a can once, he cannot go back to pick it up.

Kolsuz and Yiit want to achieve the highest *coolness points* possible. However, Kolsuz has spent a full night preparing the parkour and now is too tired to come up with the optimal parkour choreography. For a given parkour, can you help him calculate the highest possible *coolness points*?

#### Input

The number of soda cans \(\mathbf{n}\) is given in the first line.

In the next line, *coolness points* awarded for emptying the \(\mathbf{i}^{\text{th}}\) soda can, \(\mathbf{d_i}\) is given.

In the third line, \(\mathbf{dp_i}\), the number of soda cans Yiit will be unable to pick up for drinking \(\mathbf{i^{th}}\) soda can is given.

The fourth line consists of the additional *coolness points* awarded for crushing cans, \(\mathbf{c_i}\).

In the last line, \(\mathbf{cp_i}\), the number of additional soda cans Yiit will be unable to pick up for crushing \(\mathbf{i^{th}}\) soda can is given.

\(1 \leq \mathbf{n}, \mathbf{dp_i}, \mathbf{cp_i} \leq 10^5\)

\(1 \leq \mathbf{d_i}, \mathbf{c_i} \leq 100\)

#### Output

Print the highest possible *coolness points* for a given parkour.

#### Examples

Input:

```
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
```

Output:

`4`

Input:

```
4
2 3 4 5
2 1 3 4
3 2 2 1
2 2 3 4
```

Output:

`9`

#### Explanation

In the first input, Yiit can crush and drink the first soda to gain 2 (1+1) points. He becomes tired for the next 2 sodas. Then, he can crush and drink the last soda to gain 2 (1+1) more points.

In the second input, Yiit can drink the second soda to gain 3 points. He becomes tired for the next 2 sodas. Then, he can crush and drink the last soda to gain 6 (5+1) more points.