Liebig's Barrels

题意翻译

### 题目描述 你有一共m=n*k个木板。第i个木板的长度为ai。你必须用其中的每k条木板组成n个木桶。每条木板只能且必须属于一个木桶。我们把第j个木桶的最短的木板长度作为这个木桶的容积vj 你想要让这组合起来的n个木桶总容积最大。但是你需要让他们的容积尽量差不多,使得无论那两个木桶的容积差不超过l,即|vx-vy|<=l(1<=vx,vy<=n)。 输出这n个尽量相等的木桶的最大容积。如果无法组成满足要求的n个木桶,输出“0” ### 输入格式 第一行包括三个分开的整数n,k,l(1<=n,k<=10^5, 1<=n·k<=10^5, 0<=l<=10^9) 第二行包括m=n*k个整数,表示木板长度a1,a2,...,am ( 1<=ai<=10^9) ### 输出格式 输出一个整数,即n个满足要求的木桶的容积最大值 感谢@hicc0305 提供的翻译

题目描述

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. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF985C/4f1a7fe5368f5e0320d67b89ae12f92d6302564e.png)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.

输入输出格式

输入格式


The first line contains three space-separated integers $ n $ , $ k $ and $ l $ ( $ 1<=n,k<=10^{5} $ , $ 1<=n·k<=10^{5} $ , $ 0<=l<=10^{9} $ ). The second line contains $ m=n·k $ space-separated integers $ a_{1},a_{2},...,a_{m} $ ( $ 1<=a_{i}<=10^{9} $ ) — lengths of staves.

输出格式


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 $ .

输入输出样例

输入样例 #1

4 2 1
2 2 1 2 3 2 2 3

输出样例 #1

7

输入样例 #2

2 1 0
10 10

输出样例 #2

20

输入样例 #3

1 2 1
5 2

输出样例 #3

2

输入样例 #4

3 2 1
1 2 3 4 5 6

输出样例 #4

0

说明

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.