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.