{"raw_statement":[{"iden":"statement","content":"You have _m_ = _n_·_k_ wooden staves. The _i_\\-th stave has length _a__i_. You have to assemble _n_ barrels consisting of _k_ staves each, you can use any _k_ staves to construct a barrel. Each stave must belong to exactly one barrel.\n\nLet volume _v__j_ of barrel _j_ be equal to the length of the **minimal** stave in it.\n\n<center>![image](https://espresso.codeforces.com/1320351d3d4eb590d9aa6e2709b4098ace50af62.png)</center>You want to assemble exactly _n_ barrels with the maximal total sum of volumes. But you have to make them _equal enough_, so a difference between volumes of any pair of the resulting barrels must not exceed _l_, i.e. |_v__x_ - _v__y_| ≤ _l_ for any 1 ≤ _x_ ≤ _n_ and 1 ≤ _y_ ≤ _n_.\n\nPrint maximal total sum of volumes of _equal enough_ barrels or 0 if it's impossible to satisfy the condition above."},{"iden":"input","content":"The first line contains three space-separated integers _n_, _k_ and _l_ (1 ≤ _n_, _k_ ≤ 105, 1 ≤ _n_·_k_ ≤ 105, 0 ≤ _l_ ≤ 109).\n\nThe second line contains _m_ = _n_·_k_ space-separated integers _a_1, _a_2, ..., _a__m_ (1 ≤ _a__i_ ≤ 109) — lengths of staves."},{"iden":"output","content":"Print single integer — maximal total sum of the volumes of barrels or 0 if it's impossible to construct exactly _n_ barrels satisfying the condition |_v__x_ - _v__y_| ≤ _l_ for any 1 ≤ _x_ ≤ _n_ and 1 ≤ _y_ ≤ _n_."},{"iden":"examples","content":"Input\n\n4 2 1\n2 2 1 2 3 2 2 3\n\nOutput\n\n7\n\nInput\n\n2 1 0\n10 10\n\nOutput\n\n20\n\nInput\n\n1 2 1\n5 2\n\nOutput\n\n2\n\nInput\n\n3 2 1\n1 2 3 4 5 6\n\nOutput\n\n0"},{"iden":"note","content":"In the first example you can form the following barrels: \\[1, 2\\], \\[2, 2\\], \\[2, 3\\], \\[2, 3\\].\n\nIn the second example you can form the following barrels: \\[10\\], \\[10\\].\n\nIn the third example you can form the following barrels: \\[2, 5\\].\n\nIn the fourth example difference between volumes of barrels in any partition is at least 2 so it is impossible to make barrels equal enough."}],"translated_statement":[{"iden":"statement","content":"你有 #cf_span[m = n·k] 根木板。第 #cf_span[i] 根木板的长度为 #cf_span[ai]。你需要组装 #cf_span[n] 个桶，每个桶由 #cf_span[k] 根木板组成，你可以使用任意 #cf_span[k] 根木板来构造一个桶。每根木板必须恰好属于一个桶。\n\n设第 #cf_span[j] 个桶的体积 #cf_span[vj] 等于其中 *最小* 的木板长度。\n\n你希望恰好组装 #cf_span[n] 个桶，使得它们的总体积最大。但你必须让它们“足够接近”，即任意两个桶的体积之差不得超过 #cf_span[l]，也就是说，对于任意 #cf_span[1 ≤ x ≤ n] 和 #cf_span[1 ≤ y ≤ n]，都有 #cf_span[|vx - vy| ≤ l]。\n\n请输出满足上述条件的桶的最大总体积，如果无法满足条件则输出 #cf_span[0]。\n\n第一行包含三个空格分隔的整数 #cf_span[n], #cf_span[k] 和 #cf_span[l]（#cf_span[1 ≤ n, k ≤ 105], #cf_span[1 ≤ n·k ≤ 105], #cf_span[0 ≤ l ≤ 109]）。\n\n第二行包含 #cf_span[m = n·k] 个空格分隔的整数 #cf_span[a1, a2, ..., am]（#cf_span[1 ≤ ai ≤ 109]）——木板的长度。\n\n请输出一个整数：满足条件 #cf_span[|vx - vy| ≤ l]（对所有 #cf_span[1 ≤ x ≤ n] 和 #cf_span[1 ≤ y ≤ n]）的桶的最大总体积，若无法构造则输出 #cf_span[0]。\n\n在第一个例子中，你可以构造如下桶：#cf_span[[1, 2]], #cf_span[[2, 2]], #cf_span[[2, 3]], #cf_span[[2, 3]]。\n\n在第二个例子中，你可以构造如下桶：#cf_span[[10]], #cf_span[[10]]。\n\n在第三个例子中，你可以构造如下桶：#cf_span[[2, 5]]。\n\n在第四个例子中，任何划分方式下桶的体积差至少为 #cf_span[2]，因此无法使桶足够接近。"},{"iden":"input","content":"第一行包含三个空格分隔的整数 #cf_span[n], #cf_span[k] 和 #cf_span[l]（#cf_span[1 ≤ n, k ≤ 105], #cf_span[1 ≤ n·k ≤ 105], #cf_span[0 ≤ l ≤ 109]）。第二行包含 #cf_span[m = n·k] 个空格分隔的整数 #cf_span[a1, a2, ..., am]（#cf_span[1 ≤ ai ≤ 109]）——木板的长度。"},{"iden":"output","content":"请输出一个整数：满足条件 #cf_span[|vx - vy| ≤ l]（对所有 #cf_span[1 ≤ x ≤ n] 和 #cf_span[1 ≤ y ≤ n]）的桶的最大总体积，若无法构造则输出 #cf_span[0]。"},{"iden":"examples","content":"输入\n4 2 1\n2 2 1 2 3 2 2 3\n输出\n7\n\n输入\n2 1 0\n10 10\n输出\n20\n\n输入\n1 2 1\n5 2\n输出\n2\n\n输入\n3 2 1\n1 2 3 4 5 6\n输出\n0"},{"iden":"note","content":"在第一个例子中，你可以构造如下桶：#cf_span[[1, 2]], #cf_span[[2, 2]], #cf_span[[2, 3]], #cf_span[[2, 3]]。\n\n在第二个例子中，你可以构造如下桶：#cf_span[[10]], #cf_span[[10]]。\n\n在第三个例子中，你可以构造如下桶：#cf_span[[2, 5]]。\n\n在第四个例子中，任何划分方式下桶的体积差至少为 #cf_span[2]，因此无法使桶足够接近。"}],"sample_group":[],"show_order":[],"formal_statement":"Given:\n- Integers $ n, k, l $ with $ 1 \\leq n, k \\leq 10^5 $, $ n \\cdot k \\leq 10^5 $, $ 0 \\leq l \\leq 10^9 $.\n- A multiset $ A = \\{a_1, a_2, \\dots, a_{nk}\\} $ of $ nk $ positive integers representing stave lengths.\n\nDefine:\n- A **barrel** as a subset of $ k $ staves.\n- The **volume** of a barrel is the minimum length among its $ k $ staves.\n- We must partition $ A $ into exactly $ n $ disjoint barrels (each of size $ k $).\n\nConstraint:\n- For any two barrels with volumes $ v_x, v_y $, we require $ |v_x - v_y| \\leq l $.\n\nObjective:\n- Maximize the total sum of the volumes of the $ n $ barrels.\n\nIf no such partition exists satisfying the constraint, output $ 0 $.\n\n---\n\n**Formal Statement:**\n\nLet $ A = \\{a_1, a_2, \\dots, a_{nk}\\} $, sorted in non-decreasing order: $ a_1 \\leq a_2 \\leq \\dots \\leq a_{nk} $.\n\nWe seek to partition $ A $ into $ n $ disjoint subsets $ B_1, B_2, \\dots, B_n $, each of size $ k $, such that:\n\n- Let $ v_j = \\min(B_j) $ for each $ j \\in \\{1, \\dots, n\\} $.\n- $ \\max_{1 \\leq i,j \\leq n} |v_i - v_j| \\leq l $.\n- The total volume $ \\sum_{j=1}^n v_j $ is maximized.\n\nIf no such partition exists, output $ 0 $.\n\n---\n\n**Note:** Since the volume of a barrel is determined by its smallest stave, and we want to maximize the sum of volumes under a bounded range constraint, the optimal strategy involves selecting the $ n $ smallest staves that can serve as barrel minima such that their maximum difference is $ \\leq l $, and then greedily assigning the remaining staves to complete the barrels without violating the minima constraint.","simple_statement":null,"has_page_source":false}