You have?m?=?n·k?wooden staves. The?i-th stave has length?ai. You have to assemble?nbarrels 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|?≤?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?a1,?a2,?...,?am?(1?≤?ai?≤?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?|vx?-?vy|?≤?l?for any?1?≤?x?≤?n?and1?≤?y?≤?n.

Examples input Copy 4 2 1
2 2 1 2 3 2 2 3 output Copy 7 input Copy 2 1 0
10 10 output Copy 20 input Copy 1 2 1
5 2 output Copy 2 input Copy 3 2 1
1 2 3 4 5 6 output Copy 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.

?

?諸事不順，操

一個貪心，其實就是分為n堆數，每堆數的最小值相差不能大于limit ，

求出n堆數最小值的和

upper_bound 返回的是第一個大于的數，減去1就是小于等于的數了

?

1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 1e5 + 10; 4 long long a[maxn]; 5 int n, k, limit; 6 int main() { 7 scanf("%d%d%d", &n, &k, &limit); 8 for (int i = 0 ; i < n * k ; i++) 9 scanf("%lld", &a[i]); 10 sort(a, a + n * k ); 11 int temp = upper_bound(a, a + n * k, a[0] + limit) - a; 12 long long ans = 0; 13 int sum = n * k; 14 if (temp >= n) { 15 int temp1=temp; 16 while(sum > temp && sum - temp >= k - 1) { 17 sum -= k - 1; 18 ans += a[--temp1]; 19 } 20 for (int i = 0 ; i * k < temp1 ; i++) 21 ans += a[i * k]; 22 } 23 printf("%lld\n", ans); 24 return 0; 25 }

?

轉載于:https://www.cnblogs.com/qldabiaoge/p/9071432.html

總結

以上是生活随笔為你收集整理的C. Liebig's Barrels的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。