F. Cards and Joy

有 $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 \leq n \leq 500, 1 \leq k \leq 10$）——玩家人数和每位玩家将获得的牌数。 第二行包含 $k \cdot n$ 个整数 $c_1, c_2, \dots,h, c_{k \cdot n}$（$1 \leq c_i \leq 10^5$）——牌上写的数字。 第三行包含 $n$ 个整数 $f_1, f_2, \dots,h, f_n$（$1 \leq f_j \leq 10^5$）——每位玩家的最喜欢数字。 第四行包含 $k$ 个整数 $h_1, h_2, \dots,h, h_k$（$1 \leq h_t \leq 10^5$），其中 $h_t$ 表示当一位玩家恰好获得 $t$ 张写有其最喜欢数字的牌时的快乐值。保证对每个 $t \in [2..k]$，都有 $h_{t-1} < h_t$。 输出一个整数——在所有可能的分牌方式中，玩家总快乐值的最大可能值。 在第一个例子中，一种可能的最优分牌方式如下： 因此，答案是 $2 + 6 + 6 + 7 = 21$。 在第二个例子中，没有任何玩家能获得写有其最喜欢数字的牌。因此，答案是 $0$。 ## Input 输入的第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 500, 1 \leq k \leq 10$）——玩家人数和每位玩家将获得的牌数。第二行包含 $k \cdot n$ 个整数 $c_1, c_2, \dots,h, c_{k \cdot n}$（$1 \leq c_i \leq 10^5$）——牌上写的数字。第三行包含 $n$ 个整数 $f_1, f_2, \dots,h, f_n$（$1 \leq f_j \leq 10^5$）——每位玩家的最喜欢数字。第四行包含 $k$ 个整数 $h_1, h_2, \dots,h, h_k$（$1 \leq h_t \leq 10^5$），其中 $h_t$ 表示当一位玩家恰好获得 $t$ 张写有其最喜欢数字的牌时的快乐值。保证对每个 $t \in [2..k]$，都有 $h_{t-1} < h_t$。 ## Output 输出一个整数——在所有可能的分牌方式中，玩家总快乐值的最大可能值。 [samples] ## Note 在第一个例子中，一种可能的最优分牌方式如下： 玩家 $1$ 获得牌 $[1, 3, 8]$； 玩家 $2$ 获得牌 $[2, 2, 8]$； 玩家 $3$ 获得牌 $[2, 2, 8]$； 玩家 $4$ 获得牌 $[5, 5, 5]$。 因此，答案是 $2 + 6 + 6 + 7 = 21$。 在第二个例子中，没有任何玩家能获得写有其最喜欢数字的牌。因此，答案是 $0$。

Let $ n $ be the number of players, $ k $ the number of cards each player receives. Let $ C = \{c_1, c_2, \dots, c_{kn}\} $ be the multiset of card values. Let $ F = \{f_1, f_2, \dots, f_n\} $ be the multiset of players’ favorite numbers. Let $ h = (h_0, h_1, \dots, h_k) $ be the joy function, where $ h_0 = 0 $ and $ h_t > h_{t-1} $ for $ t \in [1, k] $. Define for each distinct number $ x $, let: - $ \text{count}_C(x) $: the number of cards in $ C $ with value $ x $, - $ \text{count}_F(x) $: the number of players whose favorite number is $ x $. We must assign exactly $ k $ cards to each of the $ n $ players, using all $ kn $ cards. Let $ x_1, x_2, \dots, x_m $ be the distinct values appearing in $ F $ (i.e., the favorite numbers that appear among players). For each such $ x $, suppose $ a = \text{count}_F(x) $ players have favorite number $ x $, and $ b = \text{count}_C(x) $ cards have value $ x $. We must distribute the $ b $ cards of value $ x $ among the $ a $ players who favor $ x $, and possibly also to other players (but those will contribute 0 joy for this $ x $). The goal is to assign cards to maximize total joy. For each distinct value $ x $, we must decide how to distribute the $ b $ cards of value $ x $ among the $ a $ players who favor $ x $, such that each player receives at most $ k $ cards total (but the constraint is global — we must assign exactly $ k $ cards per player overall). However, since joy is only gained when a player receives a card matching *their own* favorite number, and $ h_t $ is increasing, we can decouple the problem by value: **Key Insight**: Cards with value $ x $ only contribute to the joy of players whose favorite number is $ x $. Thus, the problem decomposes by distinct number values. For each distinct value $ x $, let: - $ a_x = |\{ j : f_j = x \}| $: number of players who favor $ x $, - $ b_x = |\{ i : c_i = x \}| $: number of cards with value $ x $. We must assign the $ b_x $ cards of value $ x $ to the $ n $ players, but only the $ a_x $ players who favor $ x $ gain joy from them. We want to assign these $ b_x $ cards to these $ a_x $ players in a way that maximizes the sum of $ h_{t_j} $, where $ t_j $ is the number of $ x $-cards received by player $ j $ (and $ t_j \leq k $), and $ \sum_{j: f_j=x} t_j \leq b_x $, and $ \sum_{j: f_j=x} t_j \leq \min(b_x, a_x \cdot k) $. But note: we are not forced to use all $ b_x $ cards on players who favor $ x $ — we could give some to others, but that yields zero joy. Since $ h_t \geq 0 $ and increasing, and we want to maximize total joy, we should assign **all** $ b_x $ cards of value $ x $ to the $ a_x $ players who favor $ x $, because giving them to others gives zero benefit. So, for each $ x $, we must distribute exactly $ b_x $ indistinguishable cards to $ a_x $ players, each player receiving between 0 and $ k $ cards, and we wish to maximize $ \sum_{j: f_j=x} h_{t_j} $, where $ \sum t_j = b_x $, $ 0 \leq t_j \leq k $. This is a **bounded knapsack** or **resource allocation** problem per value $ x $: given $ a_x $ players, each can take 0 to $ k $ cards, total cards to distribute: $ b_x $, and each player gets joy $ h_t $ if assigned $ t $ cards. Maximize total joy. Since $ k \leq 10 $, we can solve this with dynamic programming per value $ x $. Let $ \text{dp}[i][s] $ = maximum total joy achievable by distributing $ s $ cards among the first $ i $ players who favor $ x $, where each player gets between 0 and $ k $ cards. Then: - $ \text{dp}[0][0] = 0 $, $ \text{dp}[0][s] = -\infty $ for $ s > 0 $ - For $ i \in [1, a_x] $, $ s \in [0, b_x] $: $$ \text{dp}[i][s] = \max_{t=0}^{\min(k,s)} \left( \text{dp}[i-1][s - t] + h_t \right) $$ Then the total maximum joy is the sum over all distinct $ x $ of $ \text{dp}[a_x][b_x] $. Note: For values $ x $ not in $ F $, $ a_x = 0 $, so $ b_x $ cards are distributed to non-favoring players → contribute 0 joy, so we ignore them. Thus, the overall maximum total joy is: $$ \boxed{\sum_{x \in \text{distinct}(F)} \text{dp}_{x}[a_x][b_x]} $$ where $ \text{dp}_{x} $ is computed as above for value $ x $, with $ a_x = \text{count}_F(x) $, $ b_x = \text{count}_C(x) $, and $ h_0 = 0 $. **Note**: It is guaranteed that $ \sum_{x} b_x = kn $, and $ \sum_{x} a_x = n $, so the distribution is feasible.