Stepping Stones

Interview

Time limit1sMemory limit1024 MB

Summary

Find the least energy to reach the last stone using small jumps, big jumps, and one optional very big jump that costs K.

Level: Medium4 of 10
Topics: Dynamic programming, Brute force, Implementation, Array
Solved: No attempts yet

Problem

Yeongjae the ginseng digger roams around in search of wild ginseng.

While searching, Yeongjae found a riverbank with N stones lined up in a row, and learned that a wild ginseng plant lies in the gap beside the last stone.

To dig up the ginseng in the gap beside the last stone, Yeongjae moves by jumping from stone to stone. There are three kinds of jumps.

The kinds of jumps are a small jump that moves from the current position to the next stone, a big jump that skips 1 stone, and a very big jump that skips 2 stones.

Each jump consumes energy, and the energy consumed by a small jump and a big jump differs for each stone number the jump is made from.

The very big jump is given only one chance, and it consumes k energy regardless of the stone number it is made from.

Find the minimum energy Yeongjae needs to obtain the wild ginseng, since he must save as much energy as possible.

Yeongjae starts from the first stone.

Input

The first line gives the number of stones N.

Across N - 1 lines, the energy needed for a small jump and the energy needed for a big jump are given for stone 1 through stone N - 1.

The last line gives K.

Output

Print the minimum energy Yeongjae needs to obtain the wild ginseng.

Constraints

1 ≤ N ≤ 20
The energies needed for a small jump and a big jump, and K, are natural numbers not exceeding 5,000.

Examples1

Example 1
Input
```
5
1 2
2 3
4 5
6 7
4
```
Expected output
```
5
```