题目描述

有 $n$ 个史莱姆排成一行，其中第 $i$ 个的颜色为 $c_i$，质量为 $m_i$。

你可以执行任意次把一个史莱姆的质量增加 $1$ 的操作，需要花费 $w$ 的价钱。

但是一旦史莱姆的质量达到 $k$ 或以上，就会变得不稳定而必须在下一次操作之前被卖掉。你只能卖出质量大于等于 $k$ 的史莱姆。根据市场价，卖掉一个质量为 $i$ 的史莱姆可以得到 $p_i$ 的收入。保证 $p_i-p_{i-1} < w$。但不保证 $p_i$ 单调不降。

卖掉一个史莱姆之后，它两边的史莱姆会被挤压继而靠在一起。如果这两个史莱姆颜色相同，那么就会互相融合成一个史莱姆，其质量是二者的质量之和。这个新的史莱姆也有可能需要被卖掉从而接着进行这个过程。

你想知道卖掉所有史莱姆最多可以净赚多少。

输入格式

从标准输入读入数据。

第一行三个正整数 $n,k,w(1\le n\le 150, 2\le k\le 10, 1\le w\le 10^6)$。

第二行 $n$ 个正整数，其中第 $i$ 个表示 $c_i(1\le c_i\le n)$。保证 $c_i\not=c_{i-1}$。

第三行 $n$ 个正整数，其中第 $i$ 个表示 $m_i(1\le m_i < k)$。

第四行 $k-1$ 个整数，分别表示卖出质量为 $k$ 到 $2k-2$ 的史莱姆的收入，即 $p_k$ 到 $p_{2k-2}$，保证 $0\le p_i\le 10^9$，且 $p_i-p_{i-1}< w$。

保证相邻两个史莱姆的颜色不同。

输出格式

输出到标准输出。

一行一个整数，表示卖出所有史莱姆最大的净利润。

样例

输入

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

输出

-1

解释

先增加颜色为 $3$ 的史莱姆的质量。然后它被卖掉，获得 $5$ 的收入。

然后增加颜色为 $1$ 的史莱姆的质量两次。然后它被卖掉，获得 $5$ 的收入。接着两个颜色为 $2$ 的史莱姆融合在一起卖掉，获得 $7$ 的收入。

操作了三次需要 $18$ 的花费，所以净利润为 $-1$。可以证明不存在更好的方案。