{"problem":{"name":"F. Cards and Joy","description":{"content":"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 ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF999F"},"statements":[{"statement_type":"Markdown","content":"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$.\n\nThere 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.\n\nThe 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$.\n\nPrint 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.\n\n## Input\n\nThe 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.\n\nThe 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.\n\nThe 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.\n\nThe 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} &lt; h_t$ holds for each $t \\in [2..k]$.\n\n## Output\n\nPrint one integer — the maximum possible total joy levels of the players among all possible card distributions.\n\n[samples]\n\n## Note\n\nIn the first example, one possible optimal card distribution is the following:\n\n*   Player $1$ gets cards with numbers $[1, 3, 8]$;\n*   Player $2$ gets cards with numbers $[2, 2, 8]$;\n*   Player $3$ gets cards with numbers $[2, 2, 8]$;\n*   Player $4$ gets cards with numbers $[5, 5, 5]$.\n\nThus, the answer is $2 + 6 + 6 + 7 = 21$.\n\nIn the second example, no player can get a card with his favorite number. Thus, the answer is $0$.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"有 $n$ 名玩家围坐在牌桌旁。每位玩家有一个最喜欢的数字，第 $j$ 位玩家最喜欢的数字是 $f_j$。\n\n桌上有 $k \\cdot n$ 张牌，每张牌上写有一个整数：第 $i$ 张牌上的数字是 $c_i$。同时，给你一个序列 $h_1, h_2, \\dots,h_k$，其含义将在下文解释。\n\n玩家必须将所有牌分完，使得每位玩家恰好持有 $k$ 张牌。分牌完成后，每位玩家统计自己持有的牌中包含自己最喜欢数字的牌的数量。若某玩家持有 $t$ 张包含其最喜欢数字的牌，则他的快乐值为 $h_t$；若他一张这样的牌都没有（即 $t = 0$），则他的快乐值为 $0$。\n\n请输出在所有可能的分牌方式中，玩家总快乐值的最大可能值。注意，序列 $h_1, \\dots,h_k$ 对所有玩家都相同。\n\n输入的第一行包含两个整数 $n$ 和 $k$（$1 \\leq n \\leq 500, 1 \\leq k \\leq 10$）——玩家人数和每位玩家将获得的牌数。\n\n第二行包含 $k \\cdot n$ 个整数 $c_1, c_2, \\dots,h, c_{k \\cdot n}$（$1 \\leq c_i \\leq 10^5$）——牌上写的数字。\n\n第三行包含 $n$ 个整数 $f_1, f_2, \\dots,h, f_n$（$1 \\leq f_j \\leq 10^5$）——每位玩家的最喜欢数字。\n\n第四行包含 $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$。\n\n输出一个整数——在所有可能的分牌方式中，玩家总快乐值的最大可能值。\n\n在第一个例子中，一种可能的最优分牌方式如下：\n\n因此，答案是 $2 + 6 + 6 + 7 = 21$。\n\n在第二个例子中，没有任何玩家能获得写有其最喜欢数字的牌。因此，答案是 $0$。\n\n## Input\n\n输入的第一行包含两个整数 $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$。\n\n## Output\n\n输出一个整数——在所有可能的分牌方式中，玩家总快乐值的最大可能值。\n\n[samples]\n\n## Note\n\n在第一个例子中，一种可能的最优分牌方式如下：\n玩家 $1$ 获得牌 $[1, 3, 8]$；\n玩家 $2$ 获得牌 $[2, 2, 8]$；\n玩家 $3$ 获得牌 $[2, 2, 8]$；\n玩家 $4$ 获得牌 $[5, 5, 5]$。\n因此，答案是 $2 + 6 + 6 + 7 = 21$。\n在第二个例子中，没有任何玩家能获得写有其最喜欢数字的牌。因此，答案是 $0$。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ n $ be the number of players, $ k $ the number of cards each player receives.  \nLet $ C = \\{c_1, c_2, \\dots, c_{kn}\\} $ be the multiset of card values.  \nLet $ F = \\{f_1, f_2, \\dots, f_n\\} $ be the multiset of players’ favorite numbers.  \nLet $ 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] $.\n\nDefine for each distinct number $ x $, let:\n- $ \\text{count}_C(x) $: the number of cards in $ C $ with value $ x $,\n- $ \\text{count}_F(x) $: the number of players whose favorite number is $ x $.\n\nWe must assign exactly $ k $ cards to each of the $ n $ players, using all $ kn $ cards.\n\nLet $ x_1, x_2, \\dots, x_m $ be the distinct values appearing in $ F $ (i.e., the favorite numbers that appear among players).\n\nFor each such $ x $, suppose $ a = \\text{count}_F(x) $ players have favorite number $ x $, and $ b = \\text{count}_C(x) $ cards have value $ x $.\n\nWe 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 $).\n\nThe goal is to assign cards to maximize total joy.\n\nFor 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).\n\nHowever, 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:\n\n**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.\n\nFor each distinct value $ x $, let:\n- $ a_x = |\\{ j : f_j = x \\}| $: number of players who favor $ x $,\n- $ b_x = |\\{ i : c_i = x \\}| $: number of cards with value $ x $.\n\nWe 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) $.\n\nBut 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.\n\nSo, 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 $.\n\nThis 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.\n\nSince $ k \\leq 10 $, we can solve this with dynamic programming per value $ x $.\n\nLet $ \\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.\n\nThen:\n- $ \\text{dp}[0][0] = 0 $, $ \\text{dp}[0][s] = -\\infty $ for $ s > 0 $\n- For $ i \\in [1, a_x] $, $ s \\in [0, b_x] $:\n  $$\n  \\text{dp}[i][s] = \\max_{t=0}^{\\min(k,s)} \\left( \\text{dp}[i-1][s - t] + h_t \\right)\n  $$\n\nThen the total maximum joy is the sum over all distinct $ x $ of $ \\text{dp}[a_x][b_x] $.\n\nNote: 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.\n\nThus, the overall maximum total joy is:\n\n$$\n\\boxed{\\sum_{x \\in \\text{distinct}(F)} \\text{dp}_{x}[a_x][b_x]}\n$$\n\nwhere $ \\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 $.\n\n**Note**: It is guaranteed that $ \\sum_{x} b_x = kn $, and $ \\sum_{x} a_x = n $, so the distribution is feasible.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF999F","tags":["dp"],"sample_group":[["4 3\n1 3 2 8 5 5 8 2 2 8 5 2\n1 2 2 5\n2 6 7","21"],["3 3\n9 9 9 9 9 9 9 9 9\n1 2 3\n1 2 3","0"]],"created_at":"2026-03-03 11:00:39"}}