# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Tester & Editorialist:* iceknight1093

# DIFFICULTY:

1178

# PREREQUISITES:

None

# PROBLEM:

You have N songs saved on your Dotify app. The i-th song is M_i minutes long and in language L_i.

Find the longest playlist you can make if:

- Exactly K songs from these N should be chosen
- Each song should be of language L

# EXPLANATION:

We only care about songs whose language is L.

So, let’s create a list of the lengths of only these songs, say A.

We now want to choose K elements from A such that their sum is as large as possible.

So,

- If the length of A is less than K, choosing K songs is of course impossible.

In this case, the answer is`-1`

. - Otherwise, clearly it’s optimal to choose the largest K elements of A and find their sum.

A simple way to do this is to sort A and then take the sum of its last K elements.

However, the constraints here are small, so a solution in \mathcal{O}(N\cdot K) that repeats “find the maximum element in A, add it to the sum, and then remove it from A”, K times, will also get AC.

# TIME COMPLEXITY

\mathcal{O}(N\log N) or \mathcal{O}(N\cdot K) per test case.

# CODE:

## Editorialist's code (Python, sorting)

```
for _ in range(int(input())):
n, k, l = map(int, input().split())
songs = []
for i in range(n):
x, y = map(int, input().split())
if y == l: songs.append(x)
songs.sort()
songs = songs[::-1]
if len(songs) < k: print(-1)
else: print(sum(songs[:k]))
```

## Editorialist's code (Python, no sorting)

```
for _ in range(int(input())):
n, k, l = map(int, input().split())
songs = []
for i in range(n):
x, y = map(int, input().split())
if y == l: songs.append(x)
if len(songs) < k: print(-1)
else:
ans = 0
for i in range(k):
M = max(songs)
ans += M
songs.remove(M)
print(ans)
```