题目描述

新加坡每天都会举办一场活动，记 $Σ = \{1, 2, \ldots, K\}$ 表示所有可能的活动集合。参加第 $i$ 个活动可以让你的幸福值增加 $V[i]$。

假设连续 $n$ 天内举办的活动依次为 $S[1], S[2], \ldots, S[n]$（同一活动可能多次出现）。

你想依次参加 $m$ 个指定活动 $T[1], T[2], \ldots, T[m]$（同样可能重复）。因此，你计划选择某一天飞往新加坡，第 $i$ 天到达，第 $j$ 天离开。你也可以选择不去新加坡。

在新加坡停留期间，你尝试依次完成 $T[1]$ 至 $T[m]$ 的活动：

• 成功参加第 $T[i]$ 个活动，幸福值增加 $V[T[i]]$；
• 若跳过连续的 $T[p]$ 至 $T[q]$，幸福值减少 $A + (q - p + 1)B$；
• 此外，在新加坡期间，若连续 $d$ 天未参加任何活动，幸福值减少 $A + dB$。更具体地说，若你仅在第 $p$ 天和第 $q$ 天参加了活动，且 $q \geq p + 2$，中间未参加任何活动，幸福值减少 $A + (q - p - 1)B$。

你想最大化自己的幸福值。请计算最大可能的幸福值。

输入格式

第一行包含五个整数 $K, n, m, A, B$，含义如下：

• $K$：活动种类数；
• $n$：总天数；
• $m$：目标活动数量；
• $A, B$：负数，分别表示跳过惩罚参数。

第二行包含 $K$ 个正整数，第 $i$ 个整数表示第 $i$ 个活动带来的幸福值 $V[i]$。

第三行包含 $n$ 个整数，第 $i$ 个整数 $S[i]$ 表示第 $i$ 天举办的活动，范围 $1 \sim K$。

第四行包含 $m$ 个整数，第 $i$ 个整数 $T[i]$ 表示你计划依次参加的活动，范围 $1 \sim K$。

输出格式

输出一行，表示在最优安排下可以获得的最大幸福值。

1 5 3 -5 -4
10
1 1 1 1 1
1 1 1

30

1 3 5 -10 -5
10
1 1 1
1 1 1 1 1

10

4 7 4 0 0
1 2 3 4
3 1 2 1 4 1 1
1 2 3 4

7

4 8 4 0 -3
1 2 3 4
3 1 2 1 1 4 1 1
1 2 3 4

-1

4 8 4 -3 0
1 2 3 4
3 1 2 1 1 4 1 1
1 2 3 4

2

6 10 6 -2 -1
1 2 3 4 5 6
3 1 5 2 6 1 5 1 1 4
1 2 3 4 5 6

4

提示

【样例解释】

对于样例 #1：

在这个例子中，$K = 1,\ n = 5,\ m = 3,\ A = -5,\ B = -4$。 由于只有一种类型的活动，且 $m \leq n$，一种可行的最优方案是第 $1$ 天去新加坡，第 $m$ 天离开。

由于每个活动的幸福值是 $10$，且 $m = 3$，所以最优幸福值是 $30$。

对于样例 #2：

由于只有一种类型的活动，且 $n > m$，一种可行的最优方案是第 $1$ 天去新加坡，第 $n$ 天离开。 同时，我们需要跳过 $T[m - n + 1]$ 到 $T[n]$ 这几个目标活动。

由于每个活动的幸福值是 $10$，$n = 3,\ m = 5$，因此前 $3$ 个目标活动可以尝试，获得幸福值 $10 \times 3 = 30$。 跳过最后 $2$ 个目标活动，幸福值减少 $A + 2B = -10 + 2(-5) = -20$。

因此，总幸福值是 $10$。

对于样例 #3：

最优方案是尝试第 $2$ 天的 $S[2] = 1$，第 $3$ 天的 $S[3] = 2$ 和第 $5$ 天的 $S[5] = 4$。 获得的幸福值是 $1 + 2 + 4 = 7$。

对于样例 #4：

最优方案是尝试第 $5$ 天的 $S[5] = 1$ 和第 $6$ 天的 $S[6] = 4$。 幸福值是 $1 + 4 - (2 \times 3) = -1$。

对于样例 #5：

最优方案是尝试第 $5$ 天的 $S[5] = 1$ 和第 $6$ 天的 $S[6] = 4$。 跳过 $T[2]$ 和 $T[3]$，幸福值减少 $-3$。 幸福值是 $1 + 4 - 3 = 2$。

对于样例 #6：

最优方案是在第 $2$ 天到达新加坡，第 $5$ 天离开。 该方案尝试了第 $2$ 天的 $S[2] = 1$，第 $3$ 天的 $S[3] = 5$ 和第 $5$ 天的 $S[5] = 6$。 我们跳过了 $T[2]$ 到 $T[4]$，因此幸福值减少 $-2 + 3 \times (-1) = -5$。 我们跳过了第 $4$ 天，幸福值减少 $-2 + (-1) = -3$。 幸福值是 $1 + 5 + 6 - 5 - 3 = 4$。

【数据范围】

• $1 \leq K \leq 1000$
• $1 \leq n, m \leq 5000$
• $-100 \leq A, B \leq 0$
• $1 \leq V[i] \leq 100$

子任务编号	分值	额外限制
$1$	$4$	$K = 1,\ m \leq n \leq 10^3$
$2$	$6$	$K = 1,\ n < m \leq 10^3$
$3$	$12$	$A = B = 0$
$4$	$7$	$A = 0$
$5$	$8$	$B = 0$
$6$	$13$	$n,\ m < 100$
$7$	$50$	无额外限制