Background

Special for beginners, ^_^

Description

There are $N$ ponds arranged in a row ($N<100$), and each pond contains a certain number of fish. For example, when $N=5$:

That is: at pond 1 you can catch 10 fish in the first minute, only 8 fish in the second minute, ..., and after the fifth minute you can catch no more fish. It takes 3 minutes to go from pond 1 to pond 2, 5 minutes from pond 2 to pond 3, and so on.

Given a deadline $T(T<1000)$, design a fishing plan that starts from the first pond and aims to catch as many fish as possible.

Assume the number of fish you can catch depends only on how many minutes you have already spent fishing, and each unit of fishing takes an integer number of minutes.

Format

Input

There are 5 lines in total, respectively representing:

Line 1 is $N$;

Line 2 is the number of fish catchable in the first minute at each pond, separated by spaces;

Line 3 is the decrease in the number of fish caught at each pond for every additional minute, separated by spaces;

Line 4 is the time needed to go from the current pond to the next adjacent pond;

Line 5 is the deadline $T$.

Output

One integer (not exceeding $2^{31}-1$): the maximum number of fish your plan can catch.

Samples

5
10 14 20 16 9
2 4 6 5 3
3 5 4 4
14

76

Limitation

1s, 1024KiB for each test case.