Colored Slime Balls

There are $n$ slime balls arranged in a row. The $i$-th slime ball has color $c_i$ and mass $m_i$. You can perform any number of operations, each increasing the mass of one slime ball by $1$ at a cost of $w$ per operation. Once the mass of a slime ball reaches $k$ or more, it becomes unstable and must be sold before the next operation. You can only sell slime balls with mass at least $k$. Selling a slime ball with mass $i$ earns income $p_i$. It is guaranteed that $p_i - p_{i-1} < w$, but $p_i$ is not necessarily non-decreasing.

After you sell a slime ball, the slime balls on its two sides move to close the gap. If the sold ball had two neighbors of the same color, they merge into one slime ball whose mass is the sum of their masses. This new slime ball may also need to be sold, and the process continues. Find the maximum net profit after you sell all the slime balls.

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, where the $i$-th is the color $c_i$ ($1 \le c_i \le n$). It is guaranteed that $c_i \ne c_{i-1}$, so no two neighboring balls share a color initially. The third line contains $n$ positive integers, where the $i$-th is the initial mass $m_i$ ($1 \le m_i < k$). The fourth line contains $k - 1$ integers $p_k, p_{k+1}, \ldots, p_{2k-2}$ ($0 \le p_i \le 10^9$, $p_i - p_{i-1} < w$).

Print a single integer: the maximum net profit from selling all the slime balls.

In the example, first increase the mass of the slime ball with color $3$. It is then sold, earning $5$. Next, increase the mass of the slime ball with color $1$ twice. It is then sold, earning $5$. After that, the two slime balls with color $2$ merge and are sold, earning $7$. The three operations cost $18$ in total, so the net profit is $-1$. No better solution exists.