Overview

We focus on how many songs to select and how many songs to select from each genre.
We rephrase “the condition for making the bias score at most \(x\)” as an upper bound on the number of songs selected from each genre, and use DP to find the maximum total playback time achievable under that upper bound.

Analysis

First, let’s consider the condition under which, after selecting a set of songs, we can rearrange them to make the bias score at most \(x\).

Let the number of selected songs be \(s\), and the number of songs from a particular genre be \(c\).
There are \(s-c\) songs from genres other than this one.

When we arrange these \(s-c\) songs, there are \(s-c+1\) “gaps” before, after, and between them where we can place songs of this genre.

For example, if songs from other genres are represented by ○, then:

_ ○ _ ○ _ ○ _

there are \(4\) gaps.

If we want the bias score to be at most \(x\), we can place at most \(x\) songs of the same genre in each gap.
Therefore, the necessary condition is:

\[ c \leq x(s-c+1) \]

Rearranging this gives:

\[ (x+1)c \leq x(s+1) \]

So:

\[ c \leq \left\lfloor \frac{x(s+1)}{x+1} \right\rfloor \]

In fact, this condition is also a sufficient condition.
That is, if for all genres, the number of selected songs is at most

\[ \left\lfloor \frac{x(s+1)}{x+1} \right\rfloor \]

then we can arrange the \(s\) selected songs so that the bias score is at most \(x\).

Therefore, to determine whether a bias score of \(x\) is achievable, we only need to check:

For some number of songs \(s\), under the restriction of selecting at most
\(L = \left\lfloor \frac{x(s+1)}{x+1} \right\rfloor\) songs from each genre,
can we make the total playback time at least \(K\) seconds?

---

Next, let’s consider how many songs to select from each genre.

If we decide to select \(t\) songs from a certain genre, to maximize the total playback time, we should select the \(t\) songs with the longest playback times from that genre.

Therefore, for each genre, we sort the playback times in descending order and maintain prefix sums.

For example, if the playback times of songs in a certain genre are:

\[ 10, 7, 4 \]

then the prefix sums are:

\[ 0, 10, 17, 21 \]

The maximum playback time when selecting \(2\) songs from this genre is \(17\) seconds.

---

Naively enumerating all song subsets would require \(2^{2N}\) cases, which is up to \(2^{300}\) — clearly infeasible.
Also, since \(K\) can be up to \(10^9\), we cannot use playback time as a DP state.

Instead, we use “the number of selected songs” as the DP state.

Algorithm

Let \(M = 2N\).

First, consider the following DP:

\[ F[L][s] = \]

The maximum playback time when selecting exactly \(s\) songs in total, with at most \(L\) songs from each genre.

We precompute \(F[L][s]\) for all values of \(L\).

Constructing the DP

We process genre by genre.

For a given genre, let \(P\) be the prefix sums of playback times sorted in descending order.
Selecting \(t\) songs from this genre yields a maximum playback time of \(P[t]\).

However, since at most \(L\) songs can be selected from each genre:

\[ 0 \leq t \leq \min(\text{number of songs in that genre}, L) \]

The DP transition is as follows:

\[ dp_{\text{new}}[j+t] = \max(dp_{\text{new}}[j+t], dp[j] + P[t]) \]

Here:

• \(j\) is the number of songs selected so far
• \(t\) is the number of songs selected from the current genre

Performing this for all genres gives us \(F[L]\) for a fixed \(L\).

---

After that, we try bias scores \(x\) starting from \(1\) in increasing order.

For each \(x\), we try the number of selected songs \(s\) from \(1\) to \(M\).

The required per-genre upper bound is:

\[ L = \left\lfloor \frac{x(s+1)}{x+1} \right\rfloor \]

If:

\[ F[L][s] \geq K \]

then we can select a set of songs with total playback time at least \(K\) seconds, and arrange them so that the bias score is at most \(x\).

Since we check \(x\) in increasing order, the first \(x\) that satisfies the condition is the answer.

Note that if the total playback time of all songs is less than \(K\), then it is impossible to create a playlist satisfying the condition in the first place, so we output \(-1\).

Complexity

Let \(M = 2N\).

• Time complexity: \(O(M^3) = O(N^3)\)
• Space complexity: \(O(M^2) = O(N^2)\)

We perform DP for each \(L\), and there are at most \(M\) distinct values of \(L\).
The DP for a fixed \(L\) can be done in \(O(M^2)\), so the overall complexity is \(O(M^3)\).

Implementation Notes

• Sort playback times in descending order for each genre and compute prefix sums.

• In the DP, initialize impossible states with a sufficiently small value, such as \(-10^{18}\).

• \(F[L][s]\) represents the maximum playback time when selecting “exactly \(s\) songs”.
  Since the upper bound \(L\) varies with \(s\) during the bias score check, we need to manage it as “exactly” rather than “at most”.

• When \(L\) exceeds the actual maximum number of songs in any genre, the restriction no longer becomes looser, so the same DP result can be reused.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    N, K = data[0], data[1]
    M = 2 * N

    genres = [[] for _ in range(M + 1)]
    total = 0
    idx = 2
    for _ in range(M):
        b = data[idx]
        a = data[idx + 1]
        idx += 2
        genres[b].append(a)
        total += a

    if total < K:
        print(-1)
        return

    prefixes = []
    for arr in genres:
        if arr:
            arr.sort(reverse=True)
            p = [0] * (len(arr) + 1)
            s = 0
            for i, v in enumerate(arr, 1):
                s += v
                p[i] = s
            prefixes.append(p)

    prefixes.sort(key=len)

    max_cap = max(len(p) - 1 for p in prefixes)
    NEG = -10**18

    F = [None] * (M + 1)
    f0 = [NEG] * (M + 1)
    f0[0] = 0
    F[0] = f0

    for L in range(1, max_cap + 1):
        dp = [NEG] * (M + 1)
        dp[0] = 0
        max_s = 0

        for p in prefixes:
            c = len(p) - 1
            if c > L:
                c = L

            ndp = [NEG] * (M + 1)
            limit = max_s + 1
            ndp[:limit] = dp[:limit]

            dpl = dp
            ndpl = ndp

            for t in range(1, c + 1):
                add = p[t]
                j = t
                for s in range(limit):
                    v = dpl[s] + add
                    if v > ndpl[j]:
                        ndpl[j] = v
                    j += 1

            max_s += c
            dp = ndp

        F[L] = dp

    for L in range(max_cap + 1, M + 1):
        F[L] = F[max_cap]

    for x in range(1, M + 1):
        xp1 = x + 1
        for s in range(1, M + 1):
            cap = (x * (s + 1)) // xp1
            if F[cap][s] >= K:
                print(x)
                return

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.