Maximizing Net Profit by Selling Merged Slimes

You are given a row of n slimes. The i^th slime has a color c_i and an initial mass m_i.

You may perform the following operations any number of times:

• Choose one slime that is stable (its mass is strictly less than a given threshold k) and increase its mass by 1 at a cost of w.
• If after an operation a slime’s mass reaches k or above, it immediately becomes unstable and must be sold before any further operations can be performed on any slime.

Selling is only allowed when a slime is unstable (i.e. its mass is at least k). When you sell a slime of mass i, you receive a revenue of p_i. It is guaranteed that for all valid i > 1, \[ p_i - p_{i-1} < w, \] although the sequence \(p_i\) is not necessarily monotonic overall.

After a sale, the two slimes immediately adjacent to the sold slime (if both exist) become neighbors. Moreover, if these two neighbor slimes share the same color, they merge into a single slime whose mass is the sum of their masses. This merged slime will then become subject to the same rules – if its mass is at least k, it becomes unstable and must be sold before any further operations. Merging may cascade.

Your task is to determine the maximum net profit obtainable by eventually selling all the slimes. The net profit is defined as the total revenue from sales minus the total cost spent on mass‐increasing operations.

Note: Because the incremental cost is strictly greater than the revenue gain for a single unit mass increase, it is never beneficial to increase a slime’s mass beyond the minimum needed to reach k (unless merging helps you avoid extra upgrade costs).

inputFormat

The input is given as follows:

n k w
c1 c2 ... cn
 m1 m2 ... mn
V
p1 p2 ... pV

Where:

• n is the number of slimes.
• k is the stability threshold.
• w is the cost to increase a slime’s mass by 1.
• The second line gives the colors (represented as integers) of the slimes.
• The third line gives the initial masses of the slimes.
• V is an integer such that the revenue values pi are provided for i = 1, 2, ..., V. It is guaranteed that V is large enough to cover any mass that might occur after merges.
• The last line gives the revenue values: selling a slime of mass i yields revenue pi.

outputFormat

Output a single integer – the maximum net profit obtainable.

sample

1 5 10
1
3
10
1 2 3 4 10 11 12 13 14 15

-10