Visiting Singapore

Time limit2sMemory limit256 MB

Summary

Choose which days to attend so the events match T in order, paying penalties for skipped events and long idle gaps, to maximize total happiness.

Level: Medium6 of 10
Topics: Dynamic programming, String matching
Solved: No attempts yet

Problem

Singapore holds one event per day. The set of possible events is $\Sigma = \{1, 2, \ldots, K\}$ . Attending event $i$ increases your happiness by $V[i]$ . Let $S[1], \ldots, S[n]$ be the list of events held on the $n$ days, in order. The same event may appear several times in this list.

You want to attend the events $T[1], \ldots, T[m]$ in this order. The same event may also appear several times in $T$ . You may fly to Singapore on day $i$ and leave on day $j$ . You may also skip the trip entirely.

Attending $T[i]$ increases your happiness by $V[T[i]]$ . Skipping $T[p], T[p+1], \ldots, T[q]$ reduces your happiness by $A + (q-p+1)B$ .

If you go a run of $d$ consecutive days during your stay without attending any event, your happiness is reduced by $A + dB$ . Formally, if you attend $S[p]$ and $S[q]$ with $p+2 \le q$ and attend nothing in between, your happiness is reduced by $A + (q-p-1)B$ .

Find the maximum happiness you can get.

Input

The first line contains five integers $K$ , $n$ , $m$ , $A$ , and $B$ . $K$ , $n$ , and $m$ are positive integers. $A$ and $B$ are negative integers.

The second line contains $K$ positive integers $V[1], \ldots, V[K]$ .

The third line contains $n$ integers $S[1], \ldots, S[n]$ . Each is between 1 and $K$ .

The fourth line contains $m$ integers $T[1], \ldots, T[m]$ . Each is between 1 and $K$ .

Output

Print a single integer on one line: the total happiness of an optimal schedule.

Constraints

$1 \le K \le 1000$
$1 \le n, m \le 5000$
$-100 \le A, B \le 0$
$1 \le V[i] \le 100$ for all $i$ .

Examples5

Example 1
Input
```
1 5 3 -5 -4
10
1 1 1 1 1
1 1 1
```
Expected output
```
30
```
Example 2
Input
```
1 3 5 -10 -5
10
1 1 1
1 1 1 1 1
```
Expected output
```
10
```

Example 3

Input

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

Expected output

Example 4

Input

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

Expected output

-1

Example 5

Input

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

Expected output