No tag edit access

C. Liebig's Barrels

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

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* ≤ 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.

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

Examples

Input

4 2 1

2 2 1 2 3 2 2 3

Output

7

Input

2 1 0

10 10

Output

20

Input

1 2 1

5 2

Output

2

Input

3 2 1

1 2 3 4 5 6

Output

0

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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/19/2018 15:07:48 (d3).

Desktop version, switch to mobile version.

User lists

Name |
---|