English · Original
Chinese · Translation
Formal · Original
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.
Let volume _v__j_ of barrel _j_ be equal to the length of the **minimal** stave in it.
<center></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_.
Print maximal total sum of volumes of _equal enough_ barrels or 0 if it's impossible to satisfy the condition above.
## Input
The first line contains three space-separated integers _n_, _k_ and _l_ (1 ≤ _n_, _k_ ≤ 105, 1 ≤ _n_·_k_ ≤ 105, 0 ≤ _l_ ≤ 109).
The second line contains _m_ = _n_·_k_ space-separated integers _a_1, _a_2, ..., _a__m_ (1 ≤ _a__i_ ≤ 109) — lengths of staves.
## Output
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_.
[samples]
## Note
In the first example you can form the following barrels: \[1, 2\], \[2, 2\], \[2, 3\], \[2, 3\].
In the second example you can form the following barrels: \[10\], \[10\].
In the third example you can form the following barrels: \[2, 5\].
In the fourth example difference between volumes of barrels in any partition is at least 2 so it is impossible to make barrels equal enough.
你有 #cf_span[m = n·k] 根木板。第 #cf_span[i] 根木板的长度为 #cf_span[ai]。你需要组装 #cf_span[n] 个桶，每个桶由 #cf_span[k] 根木板组成，你可以使用任意 #cf_span[k] 根木板来构造一个桶。每根木板必须恰好属于一个桶。
设第 #cf_span[j] 个桶的体积 #cf_span[vj] 等于其中 *最小* 的木板长度。
你希望恰好组装 #cf_span[n] 个桶，使得它们的总体积最大。但你必须让它们“足够接近”，即任意两个桶的体积之差不得超过 #cf_span[l]，也就是说，对于任意 #cf_span[1 ≤ x ≤ n] 和 #cf_span[1 ≤ y ≤ n]，都有 #cf_span[|vx - vy| ≤ l]。
请输出满足上述条件的桶的最大总体积，如果无法满足条件则输出 #cf_span[0]。
第一行包含三个空格分隔的整数 #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]）——木板的长度。
请输出一个整数：满足条件 #cf_span[|vx - vy| ≤ l]（对所有 #cf_span[1 ≤ x ≤ n] 和 #cf_span[1 ≤ y ≤ n]）的桶的最大总体积，若无法构造则输出 #cf_span[0]。
在第一个例子中，你可以构造如下桶：#cf_span[[1, 2]], #cf_span[[2, 2]], #cf_span[[2, 3]], #cf_span[[2, 3]]。
在第二个例子中，你可以构造如下桶：#cf_span[[10]], #cf_span[[10]]。
在第三个例子中，你可以构造如下桶：#cf_span[[2, 5]]。
在第四个例子中，任何划分方式下桶的体积差至少为 #cf_span[2]，因此无法使桶足够接近。
## Input
第一行包含三个空格分隔的整数 #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]）——木板的长度。
## Output
请输出一个整数：满足条件 #cf_span[|vx - vy| ≤ l]（对所有 #cf_span[1 ≤ x ≤ n] 和 #cf_span[1 ≤ y ≤ n]）的桶的最大总体积，若无法构造则输出 #cf_span[0]。
[samples]
## Note
在第一个例子中，你可以构造如下桶：#cf_span[[1, 2]], #cf_span[[2, 2]], #cf_span[[2, 3]], #cf_span[[2, 3]]。
在第二个例子中，你可以构造如下桶：#cf_span[[10]], #cf_span[[10]]。
在第三个例子中，你可以构造如下桶：#cf_span[[2, 5]]。
在第四个例子中，任何划分方式下桶的体积差至少为 #cf_span[2]，因此无法使桶足够接近。
Given:
- Integers $ n, k, l $ with $ 1 \leq n, k \leq 10^5 $, $ n \cdot k \leq 10^5 $, $ 0 \leq l \leq 10^9 $.
- A multiset $ A = \{a_1, a_2, \dots, a_{nk}\} $ of $ nk $ positive integers representing stave lengths.
Define:
- A **barrel** as a subset of $ k $ staves.
- The **volume** of a barrel is the minimum length among its $ k $ staves.
- We must partition $ A $ into exactly $ n $ disjoint barrels (each of size $ k $).
Constraint:
- For any two barrels with volumes $ v_x, v_y $, we require $ |v_x - v_y| \leq l $.
Objective:
- Maximize the total sum of the volumes of the $ n $ barrels.
If no such partition exists satisfying the constraint, output $ 0 $.
---
**Formal Statement:**
Let $ A = \{a_1, a_2, \dots, a_{nk}\} $, sorted in non-decreasing order: $ a_1 \leq a_2 \leq \dots \leq a_{nk} $.
We seek to partition $ A $ into $ n $ disjoint subsets $ B_1, B_2, \dots, B_n $, each of size $ k $, such that:
- Let $ v_j = \min(B_j) $ for each $ j \in \{1, \dots, n\} $.
- $ \max_{1 \leq i,j \leq n} |v_i - v_j| \leq l $.
- The total volume $ \sum_{j=1}^n v_j $ is maximized.
If no such partition exists, output $ 0 $.
---
**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.
API Response (JSON)
{
"problem": {
"name": "C. Liebig's Barrels",
"description": {
"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 ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF985C"
},
"statements": [
{
"statement_type": "Markdown",
"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 ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"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] 等于其中 *最小* 的木板长度。...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "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...",
"is_translate": false,
"language": "Formal"
}
]
}