There are $n$ players sitting at the card table. Each player has a favorite number. The favorite number of the $j$-th player is $f_j$.

There are $k \cdot n$ cards on the table. Each card contains a single integer: the $i$-th card contains number $c_i$. Also, you are given a sequence $h_1, h_2, \dots, h_k$. Its meaning will be explained below.

The players have to distribute all the cards in such a way that each of them will hold exactly $k$ cards. After all the cards are distributed, each player counts the number of cards he has that contains his favorite number. The joy level of a player equals $h_t$ if the player holds $t$ cards containing his favorite number. If a player gets no cards with his favorite number (i.e., $t=0$), his joy level is $0$.

Print the maximum possible total joy levels of the players after the cards are distributed. Note that the sequence $h_1, \dots, h_k$ is the same for all the players.


-----Input-----

The first line of input contains two integers $n$ and $k$ ($1 \le n \le 500, 1 \le k \le 10$) — the number of players and the number of cards each player will get.

The second line contains $k \cdot n$ integers $c_1, c_2, \dots, c_{k \cdot n}$ ($1 \le c_i \le 10^5$) — the numbers written on the cards.

The third line contains $n$ integers $f_1, f_2, \dots, f_n$ ($1 \le f_j \le 10^5$) — the favorite numbers of the players.

The fourth line contains $k$ integers $h_1, h_2, \dots, h_k$ ($1 \le h_t \le 10^5$), where $h_t$ is the joy level of a player if he gets exactly $t$ cards with his favorite number written on them. It is guaranteed that the condition $h_{t - 1} < h_t$ holds for each $t \in [2..k]$.


-----Output-----

Print one integer — the maximum possible total joy levels of the players among all possible card distributions.


-----Examples-----
Input
4 3
1 3 2 8 5 5 8 2 2 8 5 2
1 2 2 5
2 6 7

Output
21

Input
3 3
9 9 9 9 9 9 9 9 9
1 2 3
1 2 3

Output
0



-----Note-----

In the first example, one possible optimal card distribution is the following:  Player $1$ gets cards with numbers $[1, 3, 8]$;  Player $2$ gets cards with numbers $[2, 2, 8]$;  Player $3$ gets cards with numbers $[2, 2, 8]$;  Player $4$ gets cards with numbers $[5, 5, 5]$. 

Thus, the answer is $2 + 6 + 6 + 7 = 21$.

In the second example, no player can get a card with his favorite number. Thus, the answer is $0$.

Difficulty: introductory

Starter code:

Solutions:

from queue import Queue
import sys
import math
import os.path

# CONFIG
sys.setrecursionlimit(10**9)

# LOG
def log(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


# INPUT
def ni():
    return list(map(int, input().split()))


def nio(offset):
    return [int(x) + offset for x in input().split()]


def nia():
    return list(map(int, input().split()))


# CONVERT
def toString(aList, sep=" "):
    return sep.join(str(x) for x in aList)


def mapInvertIndex(aList):
    return {k: v for v, k in enumerate(aList)}

def countMap(arr):
    m = {}
    for x in arr:
        m[x] = m.get(x,0) + 1
    return m

def sortId(arr):
    return sorted(list(range(arr)), key=lambda k: arr[k])

# MAIN

n, k = ni()
c = nia()
f = nia()
h = [0] + (nia())

cc = countMap(c)
cf = countMap(f)

n1 = n+1
k1 = k+1

nk1 = n*k+1
dp = [[0]*nk1 for _ in range(n1)]


for ni in range(1,n1):
    for ki in range(1,nk1):
        mficount = min(k,ki) + 1        
        for kii in range(mficount):
            # log(ni,ki, kii, dp[ni][ki], dp[ni-1][ki-kii] + h[kii])
            dp[ni][ki] = max(dp[ni][ki], dp[ni-1][ki-kii] + h[kii])
    # log(dp[ni])

# log(n,k)
# log("c", cc)
# log("f", cf)
# log("h", h)
# log(dp)

res = 0


for fk,fv in list(cf.items()):
    # log(fk, fv, cc.get(fk,0))
    res += dp[fv][cc.get(fk,0)]

print(res)



from queue import Queue
import sys
import math
import os.path

# CONFIG
sys.setrecursionlimit(10**9)

# LOG
def log(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


# INPUT
def ni():
    return list(map(int, input().split()))


def nio(offset):
    return [int(x) + offset for x in input().split()]


def nia():
    return list(map(int, input().split()))


# CONVERT
def toString(aList, sep=" "):
    return sep.join(str(x) for x in aList)


def mapInvertIndex(aList):
    return {k: v for v, k in enumerate(aList)}

def countMap(arr):
    m = {}
    for x in arr:
        m[x] = m.get(x,0) + 1
    return m

def sortId(arr):
    return sorted(list(range(arr)), key=lambda k: arr[k])

# MAIN

n, k = ni()
c = nia()
f = nia()
h = [0]
h.extend(nia())

cc = countMap(c)
cf = countMap(f)

n1 = n+1
k1 = k+1

nk1 = n*k+1
dp = [[0]*nk1 for _ in range(n1)]


for ni in range(1,n1):
    for ki in range(1,nk1):
        mficount = min(k,ki) + 1        
        for kii in range(mficount):
            # log(ni,ki, kii, dp[ni][ki], dp[ni-1][ki-kii] + h[kii])
            dp[ni][ki] = max(dp[ni][ki], dp[ni-1][ki-kii] + h[kii])
    # log(dp[ni])

# log(n,k)
# log("c", cc)
# log("f", cf)
# log("h", h)
# log(dp)

res = 0


for fk,fv in list(cf.items()):
    # log(fk, fv, cc.get(fk,0))
    res += dp[fv][cc.get(fk,0)]

print(res)



from queue import Queue
import sys
import math
import os.path

# CONFIG
sys.setrecursionlimit(10**9)

# LOG
def log(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


# INPUT
def ni():
    return list(map(int, input().split()))


def nio(offset):
    return [int(x) + offset for x in input().split()]


def nia():
    return list(map(int, input().split()))


# CONVERT
def toString(aList, sep=" "):
    return sep.join(str(x) for x in aList)


def mapInvertIndex(aList):
    return {k: v for v, k in enumerate(aList)}

def countMap(arr):
    m = {}
    for x in arr:
        m[x] = m.get(x,0) + 1
    return m

def sortId(arr):
    return sorted(list(range(arr)), key=lambda k: arr[k])

# MAIN

n, k = ni()
c = nia()
f = nia()
h = nia()
h.insert(0,0)

cc = countMap(c)
cf = countMap(f)

n1 = n+1
k1 = k+1

nk1 = n*k+1
dp = [[0]*nk1 for _ in range(n1)]


for ni in range(1,n1):
    for ki in range(1,nk1):
        mficount = min(k,ki) + 1        
        for kii in range(mficount):
            # log(ni,ki, kii, dp[ni][ki], dp[ni-1][ki-kii] + h[kii])
            dp[ni][ki] = max(dp[ni][ki], dp[ni-1][ki-kii] + h[kii])
    # log(dp[ni])

# log(n,k)
# log("c", cc)
# log("f", cf)
# log("h", h)
# log(dp)

res = 0


for fk,fv in list(cf.items()):
    # log(fk, fv, cc.get(fk,0))
    res += dp[fv][cc.get(fk,0)]

print(res)



from collections import Counter
from queue import Queue
import sys
import math
import os.path

# CONFIG
sys.setrecursionlimit(10**9)

# LOG
def log(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


# INPUT
def ni():
    return list(map(int, input().split()))


def nio(offset):
    return [int(x) + offset for x in input().split()]


def nia():
    return list(map(int, input().split()))


# CONVERT
def toString(aList, sep=" "):
    return sep.join(str(x) for x in aList)


def mapInvertIndex(aList):
    return {k: v for v, k in enumerate(aList)}

def sortId(arr):
    return sorted(list(range(arr)), key=lambda k: arr[k])

# MAIN

n, k = ni()
c = nia()
f = nia()
h = nia()
h.insert(0,0)

cc = Counter(c)
cf = Counter(f)

n1 = n+1
k1 = k+1

nk1 = n*k+1
dp = [[0]*nk1 for _ in range(n1)]


for ni in range(1,n1):
    for ki in range(1,nk1):
        mficount = min(k,ki) + 1        
        for kii in range(mficount):
            # log(ni,ki, kii, dp[ni][ki], dp[ni-1][ki-kii] + h[kii])
            dp[ni][ki] = max(dp[ni][ki], dp[ni-1][ki-kii] + h[kii])
    # log(dp[ni])

# log(n,k)
# log("c", cc)
# log("f", cf)
# log("h", h)
# log(dp)

res = 0


for fk,fv in list(cf.items()):
    # log(fk, fv, cc.get(fk,0))
    res += dp[fv][cc.get(fk,0)]

print(res)



from collections import Counter
from queue import Queue
import sys
import math
import os.path

# CONFIG
sys.setrecursionlimit(10**9)

# LOG
def log(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


# INPUT
def ni():
    return list(map(int, input().split()))


def nio(offset):
    return [int(x) + offset for x in input().split()]


def nia():
    return list(map(int, input().split()))


# CONVERT
def toString(aList, sep=" "):
    return sep.join(str(x) for x in aList)


def mapInvertIndex(aList):
    return {k: v for v, k in enumerate(aList)}

def sortId(arr):
    return sorted(list(range(arr)), key=lambda k: arr[k])

# MAIN

n, k = ni()
c = nia()
f = nia()
h = nia()
h.insert(0,0)

cc = Counter(c)
cf = Counter(f)

n1 = n+1
k1 = k+1

nk1 = n*k+1
dp = [[0]*nk1 for _ in range(n1)]


for ni in range(1,n1):
    for ki in range(1,nk1):
        mficount = min(k,ki) + 1        
        for kii in range(mficount):
            # log(ni,ki, kii, dp[ni][ki], dp[ni-1][ki-kii] + h[kii])
            dp[ni][ki] = max(dp[ni][ki], dp[ni-1][ki-kii] + h[kii])
    # log(dp[ni])

# log(n,k)
# log("c", cc)
# log("f", cf)
# log("h", h)
# log(dp)

res = 0


for fk,fv in list(cf.items()):
    # log(fk, fv, cc.get(fk,0))
    res += dp[fv][cc[fk]]

print(res)



from collections import Counter
from queue import Queue
import sys
import math
import os.path
sys.setrecursionlimit(10**9)
def log(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
def ni():
    return map(int, input().split())
def nio(offset):
    return map(lambda x: int(x) + offset, input().split())
def nia():
    return list(map(int, input().split()))
def toString(aList, sep=" "):
    return sep.join(str(x) for x in aList)
def mapInvertIndex(aList):
    return {k: v for v, k in enumerate(aList)}
def sortId(arr):
    return sorted(range(arr), key=lambda k: arr[k])
n, k = ni()
c = nia()
f = nia()
h = nia()
h.insert(0,0)
cc = Counter(c)
cf = Counter(f)
n1 = n+1
k1 = k+1
nk1 = n*k+1
dp = [[0]*nk1 for _ in range(n1)]
for ni in range(1,n1):
    for ki in range(1,nk1):
        mficount = min(k,ki) + 1        
        for kii in range(mficount):
            # log(ni,ki, kii, dp[ni][ki], dp[ni-1][ki-kii] + h[kii])
            dp[ni][ki] = max(dp[ni][ki], dp[ni-1][ki-kii] + h[kii])
res = 0
for fk,fv in cf.items():
    res += dp[fv][cc[fk]]
print(res)


from queue import Queue
import sys
import math
import os.path

sys.setrecursionlimit(10**9)

def log(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


def ni():
    return map(int, input().split())


def nio(offset):
    return map(lambda x: int(x) + offset, input().split())


def nia():
    return list(map(int, input().split()))


def toString(aList, sep=" "):
    return sep.join(str(x) for x in aList)


def mapInvertIndex(aList):
    return {k: v for v, k in enumerate(aList)}

def countMap(arr):
    m = {}
    for x in arr:
        m[x] = m.get(x,0) + 1
    return m

def sortId(arr):
    return sorted(range(arr), key=lambda k: arr[k])

# MAIN

n, k = ni()
c = nia()
f = nia()
h = nia()
h.insert(0,0)

cc = countMap(c)
cf = countMap(f)

n1 = n+1
k1 = k+1

nk1 = n*k+1
dp = [[0]*nk1 for _ in range(n1)]


for ni in range(1,n1):
    for ki in range(1,nk1):
        mficount = min(k,ki) + 1        
        for kii in range(mficount):
            dp[ni][ki] = max(dp[ni][ki], dp[ni-1][ki-kii] + h[kii])


res = 0


for fk,fv in cf.items():
    res += dp[fv][cc.get(fk,0)]

print(res)

import math
from collections import defaultdict


def main():
    n, k = list(map(int, input().split()))
    cards = list(map(int, input().split()))
    fav = list(map(int, input().split()))

    h = [0] + list(map(int, input().split()))

    cards_cnt = defaultdict(int)
    for val in cards:
        cards_cnt[val] += 1

    players_fav_cnt = defaultdict(int)
    for val in fav:
        players_fav_cnt[val] += 1

    # dp[a][b] - a players, b favourite cards (in total)
    dp = [[0 for _ in range(k*n+k+1)] for _ in range(n+1)]
    for p in range(n):
        for c in range(k*n+1):
            for hand in range(k+1):
                dp[p+1][c+hand] = max(dp[p+1][c+hand], dp[p][c] + h[hand])

    res = 0
    for f in players_fav_cnt:
        res += dp[players_fav_cnt[f]][cards_cnt[f]]

    print(res)


def __starting_point():
    main()

__starting_point()

def solve():
    n, k = list(map(int, input().split()))
    c = list(map(int, input().split()))
    f = list(map(int, input().split()))
    h = list(map(int, input().split()))
    cnt = {}
    for i in c:
        cnt[i] = cnt.get(i, 0) + 1
    likecolor = {}
    for i in range(n):
        likecolor.setdefault(f[i], []).append(i)
        cnt[f[i]] = cnt.get(f[i], 0)
    ans = 0
    for key, v in list(likecolor.items()):
        n1 = len(v)
        if cnt[key] >= n1 * k:
            ans += n1 * h[k - 1]
            continue
        dp = [[-float("INF")] * (cnt[key]+1) for _ in range(n1 + 1)]
        dp[0][0] = 0
        for i in range(n1):
            j = i + 1
            for e in range(cnt[key] + 1):
                dp[j][e] = max(dp[j][e], dp[i][e])
                for w in range(e + 1, min(cnt[key] + 1, e + k + 1)):
                    dp[j][w] = max(dp[i][e] + h[w - e - 1], dp[j][w])
        ans += dp[n1][cnt[key]]
    print(ans)


solve()