时间限制： 1.0 秒

空间限制： 512 MB

题目描述

小 I 经营着一个花店，其中 $n$ 盆最漂亮的花是非卖品，用于花店的装饰。方便起见，将它们从 $1$ 至 $n$ 编号。第 $i$ 盆花的魅力为 $b_i$。

为了迎客，每天小 I 都需要在 $n$ 盆花中选择一盆花摆在店门口。受花期、天气、花的种类的多样性等影响，小 I 已经决定了接下来 $m$ 天里每天摆哪一盆花，其中第 $i$ 天摆第 $a_i$ 盆花。

根据历年来的数据，小 I 预测接下来 $m-k+1$ 天里，第 $j~(1\le j\le m-k+1)$ 天将会有 $c_j$ 位顾客开始关注小 I 的花店。小 I 的花店可以打动某一位顾客，当且仅当：

• 若这个顾客在第 $x$ 天关注小 I 的花店，则在 $x,(x+1),...,(x+k-1)$ 这连续的 $k$ 天里，小 I 的花店每天摆出的花的魅力都大于等于 $V$，其中 $V$ 是一个对于所有顾客均相同的给定值。

每有一位顾客被打动，小 I 就会获得 $1$ 的收益。

为了获得更多的收益，小 I 决定今天培养一下这 $n$ 盆非卖品。具体地，小 I 可以花费 $x$ 的代价，将任意一盆花的魅力增加 $x$，其中 $x$ 为非负整数。小 I 可以使用这一方法对任意多的花增加魅力。

小 I 想知道，在如上情境下，$m$ 天后他的收益总和减去代价总和最大可以是多少。可是小 I 是花店老板不懂算法，所以需要你来帮忙。

输入格式

从标准输入读入数据。

输入的第一行包含四个非负整数 $n,m,k,V$，分别表示花的盆数、天数、打动顾客需要的连续天数、魅力值限制。

输入的第二行包含 $n$ 个非负整数 $b_1,b_2,...,b_n$，表示每盆花的魅力值。

输入的第三行包含 $m$ 个正整数 $a_1,a_2,...,a_m$，表示每天摆花的方案。

输入的第四行包含 $m-k+1$ 个非负整数 $c_1,c_2,...,c_{m-k+1}$，表示每天开始关注花店的顾客个数。

输出格式

输出到标准输出。

输出一行一个整数，表示收益总和减去代价总和的最大值。

2 3 2 10
9 10
1 1 2
2 3

4

样例 1 解释

将第一盆花的魅力值增加 $1$，这样所有 $5$ 个顾客都会被打动，收益为 $5$，代价为 $1$。容易证明没有更优的方案，因此输出为 $5-1=4$。

2 3 2 10
10 0
1 1 2
2 3

2

样例 2 解释

不做任何操作，这样第一天开始关注花店的两个顾客会被打动，而第二天开始关注花店的三个顾客不会。收益为 $2$，代价为 $0$。容易证明没有更优的方案，因此输出为 $2-0=2$。

子任务

对于所有测试数据，$1\le n\le 5000,~1\le k\le m\le 5000,~0\le b_i\le V\le 10^6,~1\le a_i\le n,~0\le c_i\le 10^7,~\sum\limits_{i=1}^{m-k+1}c_i\le 10^7$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

• 特殊性质 A : $k=m$。
• 特殊性质 B : $k=1$。
• 特殊性质 C : $n\ge m, ~\forall ~1\le i\le m,~ a_i=i$。