Bob is working on his biology assignment! He has plants in a row and needs to water all of them today. Bob wants to water the plant with milliliters of water. He can spray exactly milliliter of water onto each plant in a contiguous row of length at a cost of where and are given positive integers.

Bob is also okay with cutting some corners with his plant project. Specifically, say he ends up watering the plant with milliliters. Then he will consider as an additional cost, where is some given positive integer.

Help Bob minimize the sum of these costs!

#### Constraints

For all subtasks,

for all

##### Subtask 1 [40%]

##### Subtask 2 [60%]

#### Input Specification

The first line contains a single integer .

The next line contains three space-separated integers in that order.

The final line contains space-separated integers .

#### Output Specification

Output a single integer, the minimum possible sum of the costs.

#### Sample Input 1

```
5
1 9 8
1 1 0 1 1
```

#### Sample Output 1

`22`

#### Sample Input 2

```
8
1 2 100
2 2 0 1 0 1 1 1
```

#### Sample Output 2

`16`

## Comments