33418번 - Colored Slime Balls 다국어

문제

There are $n$ slime balls arranged in a row, where the $i$-th slime ball has color $c_i$ and mass $m_i$.

You can perform any number of operations to increase the mass of a slime ball by 1ドル,ドル and it costs $w$ per operation.

However, 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 greater than or equal to $k$. According to the market price, selling a slime ball with mass $i$ earns you income $p_i$.

It is guaranteed that $p_i - p_{i-1} < w,ドル but $p_i$ is not necessarily monotonically non-decreasing.

After you sell a slime ball, all the slime balls on its two sides move to close the gap. Moreover, if the ball you sold had two neighbors of the same color, they will merge into one slime ball whose mass is the sum of the two. This new slime ball may also need to be sold, continuing the process.

You want to know 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 integer is the color $c_i$ of the $i$-th slime ball (1ドル \le c_i \le n$). It is guaranteed that $c_i \ne c_{i-1}$. In other words, initially, there are no neighboring balls that have the same color.

The third line contains $n$ positive integers, where the $i$-th integer represents the initial mass $m_i$ of the $i$-th slime ball (1ドル \le m_i < k)$.

The fourth line contains $k - 1$ integers representing the income from selling slime balls with masses $k$ to 2ドル k - 2$. Specifically, the numbers are $p_k, p_{k + 1}, \ldots, p_{2 k - 2}$ (0ドル \le p_i \le 10^9,ドル and $p_i - p_{i - 1} < w$).

출력

Print a line with 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ドル$. Then, it is sold, earning income 5ドル$.

Then, increase the mass of the slime ball with color 1ドル$ twice. Then, it is sold, earning income 5ドル$. Next, the two slime balls with color 2ドル$ merge and are sold, earning income 7ドル$.

After three operations incurring a total cost of 18ドル,ドル the net profit is $-1$. It can be proved that there is no better solution.