以下の小問題を考えます。

各ジャンルに属する曲の数がそれぞれ多い順に \(c_1,c_2,\ldots,c_n\) 曲ずつである場合、偏りスコアの最小値はいくつになるか？

実は、この値は \(c_1\) と \(\displaystyle s=\sum_{i=1}^n c_i\) の値にのみ依存し、その値は \(\displaystyle \left\lfloor \frac{s}{s-c_1+1}\right\rfloor\) です。

このことを用いると、最も曲数の多いジャンルの曲のみ減らせると制限して良いことが分かります。また、同じジャンルの中では明らかに再生時間の短い曲から順番に減らしていけば良いです。

以上を適切に実装することでこの問題に正答することができます。計算量は \(O(N\log N)\) です。

実装例(Python3)

n, k = map(int, input().split())
n *= 2
g = [[] for _ in range(n)]
sum_a = 0
for i in range(n):
    b, a = map(int, input().split())
    g[b - 1].append(a)
    sum_a += a
if sum_a < k:
    print(-1)
    exit()
gg = max(g, key=len)
gg.sort()
m = n - len(gg) + 1
ans = n // m
for i in range(len(gg)):
    sum_a -= gg[i]
    if sum_a < k:
        break
    ans = min(ans, (n - i - 1) // m)
print(max(1, ans))