## CengTube Gazoz Boys

View as PDF

Points: 1
Time limit: 1.0s
Memory limit: 256M

Problem types

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.

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.