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$.
[{"code": "\nfrom queue import Queue\nimport sys\nimport math\nimport os.path\n\n# CONFIG\nsys.setrecursionlimit(10**9)\n\n# LOG\ndef log(*args, **kwargs):\n    print(*args, file=sys.stderr, **kwargs)\n\n\n# INPUT\ndef ni():\n    return list(map(int, input().split()))\n\n\ndef nio(offset):\n    return [int(x) + offset for x in input().split()]\n\n\ndef nia():\n    return list(map(int, input().split()))\n\n\n# CONVERT\ndef toString(aList, sep=\" \"):\n    return sep.join(str(x) for x in aList)\n\n\ndef mapInvertIndex(aList):\n    return {k: v for v, k in enumerate(aList)}\n\ndef countMap(arr):\n    m = {}\n    for x in arr:\n        m[x] = m.get(x,0) + 1\n    return m\n\ndef sortId(arr):\n    return sorted(list(range(arr)), key=lambda k: arr[k])\n\n# MAIN\n\nn, k = ni()\nc = nia()\nf = nia()\nh = [0] + (nia())\n\ncc = countMap(c)\ncf = countMap(f)\n\nn1 = n+1\nk1 = k+1\n\nnk1 = n*k+1\ndp = [[0]*nk1 for _ in range(n1)]\n\n\nfor ni in range(1,n1):\n    for ki in range(1,nk1):\n        mficount = min(k,ki) + 1        \n        for kii in range(mficount):\n            # log(ni,ki, kii, dp[ni][ki], dp[ni-1][ki-kii] + h[kii])\n            dp[ni][ki] = max(dp[ni][ki], dp[ni-1][ki-kii] + h[kii])\n    # log(dp[ni])\n\n# log(n,k)\n# log(\"c\", cc)\n# log(\"f\", cf)\n# log(\"h\", h)\n# log(dp)\n\nres = 0\n\n\nfor fk,fv in list(cf.items()):\n    # log(fk, fv, cc.get(fk,0))\n    res += dp[fv][cc.get(fk,0)]\n\nprint(res)\n", "passed": true, "time": 0.16, "memory": 14340.0, "status": "done"}, {"code": "\nfrom queue import Queue\nimport sys\nimport math\nimport os.path\n\n# CONFIG\nsys.setrecursionlimit(10**9)\n\n# LOG\ndef log(*args, **kwargs):\n    print(*args, file=sys.stderr, **kwargs)\n\n\n# INPUT\ndef ni():\n    return list(map(int, input().split()))\n\n\ndef nio(offset):\n    return [int(x) + offset for x in input().split()]\n\n\ndef nia():\n    return list(map(int, input().split()))\n\n\n# CONVERT\ndef toString(aList, sep=\" \"):\n    return sep.join(str(x) for x in aList)\n\n\ndef mapInvertIndex(aList):\n    return {k: v for v, k in enumerate(aList)}\n\ndef countMap(arr):\n    m = {}\n    for x in arr:\n        m[x] = m.get(x,0) + 1\n    return m\n\ndef sortId(arr):\n    return sorted(list(range(arr)), key=lambda k: arr[k])\n\n# MAIN\n\nn, k = ni()\nc = nia()\nf = nia()\nh = [0]\nh.extend(nia())\n\ncc = countMap(c)\ncf = countMap(f)\n\nn1 = n+1\nk1 = k+1\n\nnk1 = n*k+1\ndp = [[0]*nk1 for _ in range(n1)]\n\n\nfor ni in range(1,n1):\n    for ki in range(1,nk1):\n        mficount = min(k,ki) + 1        \n        for kii in range(mficount):\n            # log(ni,ki, kii, dp[ni][ki], dp[ni-1][ki-kii] + h[kii])\n            dp[ni][ki] = max(dp[ni][ki], dp[ni-1][ki-kii] + h[kii])\n    # log(dp[ni])\n\n# log(n,k)\n# log(\"c\", cc)\n# log(\"f\", cf)\n# log(\"h\", h)\n# log(dp)\n\nres = 0\n\n\nfor fk,fv in list(cf.items()):\n    # log(fk, fv, cc.get(fk,0))\n    res += dp[fv][cc.get(fk,0)]\n\nprint(res)\n", "passed": true, "time": 0.15, "memory": 14304.0, "status": "done"}, {"code": "\nfrom queue import Queue\nimport sys\nimport math\nimport os.path\n\n# CONFIG\nsys.setrecursionlimit(10**9)\n\n# LOG\ndef log(*args, **kwargs):\n    print(*args, file=sys.stderr, **kwargs)\n\n\n# INPUT\ndef ni():\n    return list(map(int, input().split()))\n\n\ndef nio(offset):\n    return [int(x) + offset for x in input().split()]\n\n\ndef nia():\n    return list(map(int, input().split()))\n\n\n# CONVERT\ndef toString(aList, sep=\" \"):\n    return sep.join(str(x) for x in aList)\n\n\ndef mapInvertIndex(aList):\n    return {k: v for v, k in enumerate(aList)}\n\ndef countMap(arr):\n    m = {}\n    for x in arr:\n        m[x] = m.get(x,0) + 1\n    return m\n\ndef sortId(arr):\n    return sorted(list(range(arr)), key=lambda k: arr[k])\n\n# MAIN\n\nn, k = ni()\nc = nia()\nf = nia()\nh = nia()\nh.insert(0,0)\n\ncc = countMap(c)\ncf = countMap(f)\n\nn1 = n+1\nk1 = k+1\n\nnk1 = n*k+1\ndp = [[0]*nk1 for _ in range(n1)]\n\n\nfor ni in range(1,n1):\n    for ki in range(1,nk1):\n        mficount = min(k,ki) + 1        \n        for kii in range(mficount):\n            # log(ni,ki, kii, dp[ni][ki], dp[ni-1][ki-kii] + h[kii])\n            dp[ni][ki] = max(dp[ni][ki], dp[ni-1][ki-kii] + h[kii])\n    # log(dp[ni])\n\n# log(n,k)\n# log(\"c\", cc)\n# log(\"f\", cf)\n# log(\"h\", h)\n# log(dp)\n\nres = 0\n\n\nfor fk,fv in list(cf.items()):\n    # log(fk, fv, cc.get(fk,0))\n    res += dp[fv][cc.get(fk,0)]\n\nprint(res)\n", "passed": true, "time": 0.14, "memory": 14396.0, "status": "done"}, {"code": "\nfrom collections import Counter\nfrom queue import Queue\nimport sys\nimport math\nimport os.path\n\n# CONFIG\nsys.setrecursionlimit(10**9)\n\n# LOG\ndef log(*args, **kwargs):\n    print(*args, file=sys.stderr, **kwargs)\n\n\n# INPUT\ndef ni():\n    return list(map(int, input().split()))\n\n\ndef nio(offset):\n    return [int(x) + offset for x in input().split()]\n\n\ndef nia():\n    return list(map(int, input().split()))\n\n\n# CONVERT\ndef toString(aList, sep=\" \"):\n    return sep.join(str(x) for x in aList)\n\n\ndef mapInvertIndex(aList):\n    return {k: v for v, k in enumerate(aList)}\n\ndef sortId(arr):\n    return sorted(list(range(arr)), key=lambda k: arr[k])\n\n# MAIN\n\nn, k = ni()\nc = nia()\nf = nia()\nh = nia()\nh.insert(0,0)\n\ncc = Counter(c)\ncf = Counter(f)\n\nn1 = n+1\nk1 = k+1\n\nnk1 = n*k+1\ndp = [[0]*nk1 for _ in range(n1)]\n\n\nfor ni in range(1,n1):\n    for ki in range(1,nk1):\n        mficount = min(k,ki) + 1        \n        for kii in range(mficount):\n            # log(ni,ki, kii, dp[ni][ki], dp[ni-1][ki-kii] + h[kii])\n            dp[ni][ki] = max(dp[ni][ki], dp[ni-1][ki-kii] + h[kii])\n    # log(dp[ni])\n\n# log(n,k)\n# log(\"c\", cc)\n# log(\"f\", cf)\n# log(\"h\", h)\n# log(dp)\n\nres = 0\n\n\nfor fk,fv in list(cf.items()):\n    # log(fk, fv, cc.get(fk,0))\n    res += dp[fv][cc.get(fk,0)]\n\nprint(res)\n", "passed": true, "time": 0.15, "memory": 14360.0, "status": "done"}, {"code": "\nfrom collections import Counter\nfrom queue import Queue\nimport sys\nimport math\nimport os.path\n\n# CONFIG\nsys.setrecursionlimit(10**9)\n\n# LOG\ndef log(*args, **kwargs):\n    print(*args, file=sys.stderr, **kwargs)\n\n\n# INPUT\ndef ni():\n    return list(map(int, input().split()))\n\n\ndef nio(offset):\n    return [int(x) + offset for x in input().split()]\n\n\ndef nia():\n    return list(map(int, input().split()))\n\n\n# CONVERT\ndef toString(aList, sep=\" \"):\n    return sep.join(str(x) for x in aList)\n\n\ndef mapInvertIndex(aList):\n    return {k: v for v, k in enumerate(aList)}\n\ndef sortId(arr):\n    return sorted(list(range(arr)), key=lambda k: arr[k])\n\n# MAIN\n\nn, k = ni()\nc = nia()\nf = nia()\nh = nia()\nh.insert(0,0)\n\ncc = Counter(c)\ncf = Counter(f)\n\nn1 = n+1\nk1 = k+1\n\nnk1 = n*k+1\ndp = [[0]*nk1 for _ in range(n1)]\n\n\nfor ni in range(1,n1):\n    for ki in range(1,nk1):\n        mficount = min(k,ki) + 1        \n        for kii in range(mficount):\n            # log(ni,ki, kii, dp[ni][ki], dp[ni-1][ki-kii] + h[kii])\n            dp[ni][ki] = max(dp[ni][ki], dp[ni-1][ki-kii] + h[kii])\n    # log(dp[ni])\n\n# log(n,k)\n# log(\"c\", cc)\n# log(\"f\", cf)\n# log(\"h\", h)\n# log(dp)\n\nres = 0\n\n\nfor fk,fv in list(cf.items()):\n    # log(fk, fv, cc.get(fk,0))\n    res += dp[fv][cc[fk]]\n\nprint(res)\n", "passed": true, "time": 0.15, "memory": 14256.0, "status": "done"}, {"code": "\nfrom collections import Counter\nfrom queue import Queue\nimport sys\nimport math\nimport os.path\nsys.setrecursionlimit(10**9)\ndef log(*args, **kwargs):\n    print(*args, file=sys.stderr, **kwargs)\ndef ni():\n    return map(int, input().split())\ndef nio(offset):\n    return map(lambda x: int(x) + offset, input().split())\ndef nia():\n    return list(map(int, input().split()))\ndef toString(aList, sep=\" \"):\n    return sep.join(str(x) for x in aList)\ndef mapInvertIndex(aList):\n    return {k: v for v, k in enumerate(aList)}\ndef sortId(arr):\n    return sorted(range(arr), key=lambda k: arr[k])\nn, k = ni()\nc = nia()\nf = nia()\nh = nia()\nh.insert(0,0)\ncc = Counter(c)\ncf = Counter(f)\nn1 = n+1\nk1 = k+1\nnk1 = n*k+1\ndp = [[0]*nk1 for _ in range(n1)]\nfor ni in range(1,n1):\n    for ki in range(1,nk1):\n        mficount = min(k,ki) + 1        \n        for kii in range(mficount):\n            # log(ni,ki, kii, dp[ni][ki], dp[ni-1][ki-kii] + h[kii])\n            dp[ni][ki] = max(dp[ni][ki], dp[ni-1][ki-kii] + h[kii])\nres = 0\nfor fk,fv in cf.items():\n    res += dp[fv][cc[fk]]\nprint(res)", "passed": true, "time": 0.15, "memory": 14456.0, "status": "done"}, {"code": "\nfrom queue import Queue\nimport sys\nimport math\nimport os.path\n\nsys.setrecursionlimit(10**9)\n\ndef log(*args, **kwargs):\n    print(*args, file=sys.stderr, **kwargs)\n\n\ndef ni():\n    return map(int, input().split())\n\n\ndef nio(offset):\n    return map(lambda x: int(x) + offset, input().split())\n\n\ndef nia():\n    return list(map(int, input().split()))\n\n\ndef toString(aList, sep=\" \"):\n    return sep.join(str(x) for x in aList)\n\n\ndef mapInvertIndex(aList):\n    return {k: v for v, k in enumerate(aList)}\n\ndef countMap(arr):\n    m = {}\n    for x in arr:\n        m[x] = m.get(x,0) + 1\n    return m\n\ndef sortId(arr):\n    return sorted(range(arr), key=lambda k: arr[k])\n\n# MAIN\n\nn, k = ni()\nc = nia()\nf = nia()\nh = nia()\nh.insert(0,0)\n\ncc = countMap(c)\ncf = countMap(f)\n\nn1 = n+1\nk1 = k+1\n\nnk1 = n*k+1\ndp = [[0]*nk1 for _ in range(n1)]\n\n\nfor ni in range(1,n1):\n    for ki in range(1,nk1):\n        mficount = min(k,ki) + 1        \n        for kii in range(mficount):\n            dp[ni][ki] = max(dp[ni][ki], dp[ni-1][ki-kii] + h[kii])\n\n\nres = 0\n\n\nfor fk,fv in cf.items():\n    res += dp[fv][cc.get(fk,0)]\n\nprint(res)", "passed": true, "time": 0.14, "memory": 14300.0, "status": "done"}, {"code": "import math\nfrom collections import defaultdict\n\n\ndef main():\n    n, k = list(map(int, input().split()))\n    cards = list(map(int, input().split()))\n    fav = list(map(int, input().split()))\n\n    h = [0] + list(map(int, input().split()))\n\n    cards_cnt = defaultdict(int)\n    for val in cards:\n        cards_cnt[val] += 1\n\n    players_fav_cnt = defaultdict(int)\n    for val in fav:\n        players_fav_cnt[val] += 1\n\n    # dp[a][b] - a players, b favourite cards (in total)\n    dp = [[0 for _ in range(k*n+k+1)] for _ in range(n+1)]\n    for p in range(n):\n        for c in range(k*n+1):\n            for hand in range(k+1):\n                dp[p+1][c+hand] = max(dp[p+1][c+hand], dp[p][c] + h[hand])\n\n    res = 0\n    for f in players_fav_cnt:\n        res += dp[players_fav_cnt[f]][cards_cnt[f]]\n\n    print(res)\n\n\ndef __starting_point():\n    main()\n\n__starting_point()", "passed": true, "time": 0.14, "memory": 14292.0, "status": "done"}, {"code": "def solve():\n    n, k = list(map(int, input().split()))\n    c = list(map(int, input().split()))\n    f = list(map(int, input().split()))\n    h = list(map(int, input().split()))\n    cnt = {}\n    for i in c:\n        cnt[i] = cnt.get(i, 0) + 1\n    likecolor = {}\n    for i in range(n):\n        likecolor.setdefault(f[i], []).append(i)\n        cnt[f[i]] = cnt.get(f[i], 0)\n    ans = 0\n    for key, v in list(likecolor.items()):\n        n1 = len(v)\n        if cnt[key] >= n1 * k:\n            ans += n1 * h[k - 1]\n            continue\n        dp = [[-float(\"INF\")] * (cnt[key]+1) for _ in range(n1 + 1)]\n        dp[0][0] = 0\n        for i in range(n1):\n            j = i + 1\n            for e in range(cnt[key] + 1):\n                dp[j][e] = max(dp[j][e], dp[i][e])\n                for w in range(e + 1, min(cnt[key] + 1, e + k + 1)):\n                    dp[j][w] = max(dp[i][e] + h[w - e - 1], dp[j][w])\n        ans += dp[n1][cnt[key]]\n    print(ans)\n\n\nsolve()\n", "passed": true, "time": 0.15, "memory": 14460.0, "status": "done"}]