Hike

Interview

Time limit1sMemory limit1024 MB

Summary

Given the altitude sequence of a route and the energy costs of climbing, descending, and resting, find the total time for a hike that starts and ends at sea level.

Level: Easy3 of 10
Topics: Simulation, Implementation
Solved: No attempts yet

Problem

Vytis the hiker plans to walk through the mountains today. Using a relief map, he chose a route described by the sequence of altitudes of its points. When walking from point i to point i + 1, Vytis climbs or descends by the difference in altitude. If the two points are at the same altitude, he walks straight ahead. Vytis starts and ends his hike at sea level (altitude 0).

Walking, climbing, or descending one meter takes Vytis one time unit. His energy changes as follows:

After breakfast, his energy is $E_0$ .
Each meter climbed uses $E_u$ energy.
Each meter descended uses $E_n$ energy.
Walking straight ahead uses no energy. However, if he has no energy at all, he cannot walk straight ahead.
If he runs out of energy during the hike, he sits down to rest. While resting, he gains $E_g$ energy per time unit.

For example, let $E_0 = 6$ , $E_u = 3$ , $E_n = 1$ , and $E_g = 1$ . Vytis plans to climb the mountain shown below.

Figure 1. The right side shows the altitude, and the route points are listed below the figure.

He climbs to the first point. This takes 1 time unit and uses 3 energy.
He climbs to the second point. This takes 1 time unit and uses 3 energy.
He has no energy left, so he rests here. After resting, he gains 1 energy. The rest takes 1 time unit.
He walks straight to the third point. This takes 1 time unit and uses no energy.
He does not have enough energy to descend from the third point, so he rests for 1 more time unit.
He descends from the third point. This takes 2 time units and uses 2 energy.

In total, Vytis travels for 7 time units. Of these, 5 are spent walking, climbing, or descending, and 2 are spent resting.

Assume Vytis starts his hike after eating breakfast. Find how many time units the hike takes.

Input

The first line contains four integers $E_0$ , $E_u$ , $E_n$ , and $E_g$ , which mean the following.

$E_0$ : Vytis's energy after breakfast
$E_u$ : energy used per meter climbed
$E_n$ : energy used per meter descended
$E_g$ : energy gained per time unit of rest

The second line contains the route length $N$ . The next $N$ lines give the altitudes $h_i$ in order.

Output

Print one integer, the number of time units the hike takes.

Constraints

$1 \le E_0, E_g, E_u, E_n \le 1\,000$
$1 \le N \le 100\,000$
$1 \le h_i \le 10\,000$

Examples2

Example 1
Input
```
4 2 1 1
3
1
2
2
```
Expected output
```
7
```
Example 2
Input
```
1 2 1 2
4
1
2
4
2
```
Expected output
```
14
```