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

You can perform an operation to increase the mass of a slime by $1$ at a cost of $w$.

However, once a slime's mass reaches $k$ or more, it becomes unstable and must be sold before any further operations can be performed. You can only sell slimes with a mass of at least $k$. According to the market price, selling a slime of mass $i$ yields a profit of $p_i$. It is guaranteed that $p_i - p_{i-1} < w$. Note that $p_i$ is not guaranteed to be monotonically non-decreasing.

After a slime is sold, the slimes on either side of it are pushed together. If these two slimes have the same color, they will merge into a single slime with a mass equal to the sum of their masses. This new slime may also need to be sold, potentially triggering the process again.

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

Input

The input is read from standard input.

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 represents $c_i$ ($1 \le c_i \le n$). It is guaranteed that $c_i \neq c_{i-1}$.

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

The fourth line contains $k-1$ integers representing the revenue from selling slimes with masses from $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 adjacent slimes have different colors.

Output

Output to standard output.

A single integer representing the maximum net profit from selling all slimes.

Examples

Input 1

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

Output 1

-1

Note 1

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

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

Three operations were performed at a cost of $18$, resulting in a net profit of $-1$. It can be proven that no better strategy exists.