Educational Codeforces Round 44 (Rated for Div. 2)

2018-06-29

Educational Codeforces Round 44 (Rated for Div 2) 。

C. Liebig&#39;s Barrelstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You have m=n·k wooden staves. The i-th stave has length ai. 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 vj 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. |vx-vy|&le;l for any 1&le;x&le;n and 1&le;y&le;n.

Print maximal total sum of volumes of equal enough barrels or 0 if it&#39;s impossible to satisfy the condition above.

Input

The first line contains three space-separated integers n, k and l (1&le;n,k&le;105, 1&le;n·k&le;105, 0&le;l&le;109).

The second line contains m=n·k space-separated integers a1,a2,...,am (1&le;ai&le;109) — lengths of staves.

Output

Print single integer — maximal total sum of the volumes of barrels or 0 if it&#39;s impossible to construct exactly n barrels satisfying the condition |vx-vy|&le;l for any 1&le;x&le;n and 1&le;y&le;n.

ExamplesInputCopy
```4 2 1
2 2 1 2 3 2 2 3
```
OutputCopy
```7
```
InputCopy
```2 1 0
10 10
```
OutputCopy
```20
```
InputCopy
```1 2 1
5 2
```
OutputCopy
```2
```
InputCopy
```3 2 1
1 2 3 4 5 6
```
OutputCopy
```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.

```#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
LL arr[100010];
LL tem[100010];

int main()
{
LL sum=0;
LL n,k;
LL l;
cin>>n>>k>>l;
for(LL i=1;i<=n*k;i++)
{
cin>>arr[i];
}
sort(arr+1,arr+1+n*k);
LL j=0;
tem[++j]=1;
int ans;
for(LL i=1;i<=n*k;i++)
{
if(arr[i+1]!=arr[i])
tem[++j]=i;
else tem[j]=i;
if(arr[i]==l+arr[1])
ans=i;
else if(arr[i]
```