싱가포르 방문

싱가포르에서는 하루에 행사가 하나씩 열린다. 행사의 집합은 $\Sigma = \{1, 2, \ldots, K\}$이다. 행사 $i$에 참석하면 행복도가 $V[i]$만큼 증가한다. $n$일 동안 순서대로 열리는 행사를 $S[1], \ldots, S[n]$이라 하자. 같은 행사가 이 목록에 여러 번 나타날 수 있다.

여러분은 행사 $T[1], \ldots, T[m]$에 이 순서대로 참석하려고 한다. $T$에도 같은 행사가 여러 번 나타날 수 있다. $i$일에 싱가포르로 떠나 $j$일에 떠날 계획을 세울 수 있다. 싱가포르에 아예 가지 않을 수도 있다.

$T[i]$에 참석하면 행복도가 $V[T[i]]$만큼 증가한다. $T[p], T[p+1], \ldots, T[q]$를 건너뛰면 행복도가 $A + (q-p+1)B$만큼 줄어든다.

체류 중 $d$일 연속으로 행사에 참석하지 않으면 행복도가 $A + dB$만큼 줄어든다. 공식으로 말하면, $S[p]$와 $S[q]$에 참석하고 $p+2 \le q$이며 그 사이에는 아무 행사에도 참석하지 않았다면 행복도가 $A + (q-p-1)B$만큼 줄어든다.

얻을 수 있는 최대 행복도를 구하라.

첫 줄에 다섯 정수 $K$, $n$, $m$, $A$, $B$가 주어진다. $K$, $n$, $m$은 양의 정수이고, $A$와 $B$는 음의 정수이다.

둘째 줄에는 $K$개의 양의 정수 $V[1], \ldots, V[K]$가 주어진다.

셋째 줄에는 $n$개의 정수 $S[1], \ldots, S[n]$이 주어진다. 각 값은 1 이상 $K$ 이하이다.

넷째 줄에는 $m$개의 정수 $T[1], \ldots, T[m]$이 주어진다. 각 값은 1 이상 $K$ 이하이다.

최적 일정에서의 총 행복도를 나타내는 정수 하나를 한 줄에 출력한다.

• $1 \le K \le 1000$
• $1 \le n, m \le 5000$
• $-100 \le A, B \le 0$
• 모든 $i$에 대해 $1 \le V[i] \le 100$이다.