Description

There are N fish ponds arranged in a row (N < 100), each containing a certain number of fish.
For example, when N = 5, the table is as follows:

That is: In the first pond, you can catch 10 fish in the first minute, 8 fish in the second minute, ..., and no fish after the 5th minute. It takes 3 minutes to go from the first pond to the second pond, 5 minutes from the second pond to the third pond, and so on.

Given a deadline T (T < 1000), design a fishing plan starting from the first pond to catch the maximum number of fish.
Assume the number of fish caught depends only on the number of fishing attempts made, and each fishing attempt takes an integer number of minutes.

Input Format

There are 5 lines of input:

• Line 1: N;
• Line 2: The number of fish that can be caught in the first minute for each pond, separated by spaces;
• Line 3: The reduction in the number of fish caught per minute for each pond, separated by spaces;
• Line 4: The time required to travel from the current pond to the next adjacent pond, separated by spaces;
• Line 5: The deadline T.

Output Format

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

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

76