牌桌上坐着 $$$n$$$ 玩家。每个玩家都有一个最喜欢的号码。第 $$$j$$$ 位玩家最喜欢的号码是 $$$f_j$$$。
桌子上有 $$$k \cdot n$$$ 牌。每张卡包含一个整数:第 $$$i$$$ 卡包含数字 $$$c_i$$$。此外,还会给您一个序列 $$$h_1, h_2, \dots, h_k$$$。下面将解释其含义。
玩家必须以这样的方式分发所有卡片,使得每个人都持有恰好 $$$k$$$ 的卡片。当所有的牌都分发完后,每个玩家都会计算他拥有的包含他最喜欢的数字的牌的数量。如果玩家持有包含他最喜欢的数字的 $$$t$$$ 卡,则玩家的快乐程度等于 $$$h_t$$$。如果玩家没有拿到带有他最喜欢的数字的牌(即 $$$t=0$$$),则他的快乐程度为 $$$0$$$。
打印卡片分发后玩家可能的最大总欢乐程度。请注意,序列 $$$h_1, \dots, h_k$$$ 对于所有玩家来说都是相同的。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 500, 1 \le k \le 10$$$) — 玩家数量和每个玩家将获得的牌数。
第二行包含 $$$k \cdot n$$$ 整数 $$$c_1, c_2, \dots, c_{k \cdot n}$$$ ($$$1 \le c_i \le 10^5$$$) — 写在卡片上的数字。
第三行包含 $$$n$$$ 整数 $$$f_1, f_2, \dots, f_n$$$ ($$$1 \le f_j \le 10^5$$$) — 玩家最喜欢的号码。
第四行包含 $$$k$$$ 整数 $$$h_1, h_2, \dots, h_k$$$ ($$$1 \le h_t \le 10^5$$$),其中 $$$h_t$$$ 是玩家在获得恰好 $$$t$$$ 牌上写有他最喜欢的数字时的快乐程度。保证条件 $$$h_{t - 1} < h_t$$$ 对于 [2..k]$$$ 中的每个 $$$t \ 成立。
输出
打印一个整数——所有可能的卡牌分布中玩家可能的最大总快乐度。
示例
输入 #1
4 3 1 3 2 8 5 5 8 2 2 8 5 2 1 2 2 5 2 6 7
输出 #1
21
输入 #2
3 3 9 9 9 9 9 9 9 9 9 1 2 3 1 2 3
输出 #2
0
注意
在第一个示例中,一种可能的最佳卡片分配如下:
- 玩家 $$$1$$$ 获得数字为 $$$[1, 3, 8]$$$ 的牌;
- 玩家 $$$2$$$ 获得数字为 $$$[2, 2, 8]$$$ 的牌;
- 玩家 $$$3$$$ 获得数字为 $$$[2, 2, 8]$$$ 的牌;
- 玩家 $$$4$$$ 获得数字为 $$$[5, 5, 5]$$$ 的牌。
因此,答案是 $$$2 + 6 + 6 + 7 = 21$$$。
在第二个例子中,没有玩家可以获得带有他最喜欢的数字的牌。因此,答案是$$$0$$$。