985C.md (2229B)
1 Source: https://codeforces.com/problemset/problem/985/C 2 3 C. Liebig's Barrels 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 Let volume *v**j* of barrel *j* be equal to the length of the minimal stave in it. 24 25  26 27 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*. 28 29 Print maximal total sum of volumes of equal enough barrels or 0 if it's impossible to satisfy the condition above. 30 31 Input 32 33 The first line contains three space-separated integers *n*, *k* and *l* (1 ≤ *n*, *k* ≤ 105, 1 ≤ *n*·*k* ≤ 105, 0 ≤ *l* ≤ 109). 34 35 The second line contains *m* = *n*·*k* space-separated integers *a*1, *a*2, ..., *a**m* (1 ≤ *a**i* ≤ 109) — lengths of staves. 36 37 Output 38 39 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*. 40 41 Examples 42 43 Input 44 45 ``` 46 4 2 1 47 2 2 1 2 3 2 2 3 48 ``` 49 50 Output 51 52 ``` 53 7 54 ``` 55 56 Input 57 58 ``` 59 2 1 0 60 10 10 61 ``` 62 63 Output 64 65 ``` 66 20 67 ``` 68 69 Input 70 71 ``` 72 1 2 1 73 5 2 74 ``` 75 76 Output 77 78 ``` 79 2 80 ``` 81 82 Input 83 84 ``` 85 3 2 1 86 1 2 3 4 5 6 87 ``` 88 89 Output 90 91 ``` 92 0 93 ``` 94 95 Note 96 97 In the first example you can form the following barrels: [1, 2], [2, 2], [2, 3], [2, 3]. 98 99 In the second example you can form the following barrels: [10], [10]. 100 101 In the third example you can form the following barrels: [2, 5]. 102 103 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.