Problem Description

There are $n$ slimes in a line. The color of the $i$-th slime is $c_i$, and its mass is $m_i$.

You may perform the operation of increasing the mass of one slime by $1$ any number of times, which costs $w$ each time.

However, once a slime’s mass reaches $k$ or above, it becomes unstable and must be sold before the next operation. You can only sell slimes whose mass is greater than or equal to $k$. According to the market price, selling a slime of mass $i$ yields an income of $p_i$. It is guaranteed that $p_i - p_{i-1} < w$. However, $p_i$ is not guaranteed to be non-decreasing.

After selling a slime, the slimes on its two sides will be squeezed together and become adjacent. If these two slimes have the same color, they will merge into one slime whose mass is the sum of their masses. This new slime may also need to be sold, and the process may continue.

You want to know the maximum net profit you can earn by selling all slimes.

Input Format

The first line contains three positive integers $n, k, w \ (1 \le n \le 150, 2 \le k \le 10, 1 \le w \le 10^6)$.

The second line contains $n$ positive integers. The $i$-th integer is $c_i \ (1 \le c_i \le n)$. It is guaranteed that $c_i \not= c_{i-1}$.

The third line contains $n$ positive integers. The $i$-th integer is $m_i \ (1 \le m_i < k)$.

The fourth line contains $k - 1$ integers, which represent the income for selling slimes of mass $k$ to $2k - 2$, i.e. $p_k$ to $p_{2k-2}$. It is guaranteed that $0 \le p_i \le 10^9$, and $p_i - p_{i-1} < w$.

It is guaranteed that the colors of any two adjacent slimes are different.

Output Format

Output one integer in one line, representing the maximum net profit from selling all slimes.

4 5 6
2 1 2 3
3 3 3 4
5 7 9 11

-1

Hint

First, increase the mass of the slime with color $3$. Then it is sold, yielding an income of $5$.

Then increase the mass of the slime with color $1$ twice. Then it is sold, yielding an income of $5$. Next, the two slimes with color $2$ merge and are sold, yielding an income of $7$.

Three operations cost $18$, so the net profit is $-1$. It can be proven that there is no better plan.

Translated by ChatGPT 5