← 返回题目列表

Codeforces · 985/C

C. 李比希的桶

中文机器翻译题面 查看原题

你有 m = n·k 根木棍。第 i 个板条的长度为 ai。您必须组装 n 个桶,每个桶由 k 个板条组成,您可以使用任何 k 个板条来构造一个桶。每根木板必须恰好属于一个木桶。

令桶 j 的体积 vj 等于其中最小板条的长度。

您想要组装 n 个具有最大总体积的桶。但你必须使它们足够相等,因此任何一对所得桶的体积之间的差异不得超过l,即|vx - vy| ≤ l 对于任何 1 ≤ x ≤ n 和 1 ≤ y ≤ n。

打印足够数量的桶的最大体积总和,如果不可能满足上述条件,则打印 0。

输入

第一行包含三个空格分隔的整数 n、k 和 l (1 ≤ n, k ≤ 105, 1 ≤ n·k ≤ 105, 0 ≤ l ≤ 109)。

第二行包含 m = n·k 个空格分隔的整数 a1, a2, ..., am (1 ≤ ai ≤ 109) — 谱表的长度。

输出

打印单个整数 - 桶体积的最大总和或 0(如果不可能构造恰好 n 个满足条件 |vx - vy| 的桶) ≤ l 对于任何 1 ≤ x ≤ n 和 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

注意

在第一个示例中,您可以形成以下桶:[1, 2]、[2, 2]、[2, 3]、[2, 3]。

在第二个示例中,您可以形成以下桶:[10]、[10]。

在第三个示例中,您可以形成以下桶:[2, 5]。

在第四个示例中,任何分区中桶的体积之间的差异至少为 2,因此不可能使桶足够相等。