# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author, Tester, and Editorialist:* iceknight1093

# DIFFICULTY:

TBD

# PREREQUISITES:

Sorting

# PROBLEM:

K people line up to buy N pastries from a shop. You’re L-th in line.

The pastries have deliciousness values A_1, A_2, \ldots, A_N.

On their turn, a person will always pick the most delicious remaining pastry; then move to the back of the line.

Find the total deliciousness of pastries you buy.

# EXPLANATION:

Let’s sort the array A, so that A_1 \geq A_2 \geq \ldots \geq A_N.

Then, notice that:

- The first person will choose A_1
- The second person will choose A_2
- The third person will choose A_3

\vdots - The K-th person will choose A_K
- Then, it’s the first person’s turn again, who will pick A_{K+1}
- The second person gets another turn, and picks A_{K+2}

\vdots

In general, the i-th person in line will pick A_i, A_{i+K}, A_{i+2K}, \ldots.

You’re L-th in line, so you’ll pick A_L, A_{L+K}, A_{L+2K}, \ldots

Simply print the sum of these numbers.

Since N can be as large as 2\cdot 10^5 in this task, sorting A needs to be done in \mathcal{O}(N\log N) using an efficient algorithm, such as mergesort or quicksort; \mathcal{O}(N^2) sort algorithms such as bubble sort and insertion sort won’t be fast enough.

The simplest way is to just use your language’s built-in sort function.

# TIME COMPLEXITY

\mathcal{O}(N\log N) per testcase.

# CODE:

## Editorialist's code (Python)

```
for _ in range(int(input())):
n, k, l = map(int, input().split())
a = sorted(list(map(int, input().split())))[::-1]
print(sum(a[l-1::k]))
```