p549.ans1
======================
2 22

=================
p549.ans2
======================
1 10

=================
p549.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, k;
vector<pair<int, int>> dumbbells;

void read() {
    cin >> n >> k;
    dumbbells.resize(n);
    cin >> dumbbells;
}

void solve() {
    // Each set fixes a multiset of k distinct masses shared by every set, so a
    // mass can contribute one dumbbell to each of the t sets only if it has at
    // least t dumbbells. Group costs by mass; the number of sets t is limited
    // to k (k distinct masses per set) and to how many masses are frequent
    // enough, so the best t is the count of the k-th most frequent mass: with
    // that t we have at least k masses each owning >= t dumbbells.
    //
    // For each eligible mass (count >= t) take its t most expensive dumbbells
    // and sum them; we then pick the k masses with the largest such sums to
    // maximize total cost. If there are fewer than k distinct masses no set
    // can be formed and the answer is 0 0.

    map<int, vector<int>> mass_to_costs;
    for(auto [m, c]: dumbbells) {
        mass_to_costs[m].push_back(c);
    }

    vector<pair<int, int>> frequency;
    for(auto& [mass, costs]: mass_to_costs) {
        sort(costs.rbegin(), costs.rend());
        frequency.push_back({(int)costs.size(), mass});
    }

    sort(frequency.rbegin(), frequency.rend());

    if((int)frequency.size() < k) {
        cout << 0 << ' ' << 0 << '\n';
        return;
    }

    int t = frequency[k - 1].first;

    vector<int64_t> selected;
    for(auto [count, mass]: frequency) {
        if(count < t) {
            break;
        }

        int64_t sum_costs = 0;
        for(int i = 0; i < t; i++) {
            sum_costs += mass_to_costs[mass][i];
        }

        selected.push_back(sum_costs);
    }

    sort(selected.rbegin(), selected.rend());

    int64_t total = 0;
    for(int i = 0; i < k; i++) {
        total += selected[i];
    }

    cout << t << ' ' << total << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p549.in1
======================
7 2
16 1
4 6
16 7
7 100
32 9
4 6
32 1

=================
p549.in2
======================
4 2
1 2
2 1
4 3
1 7

=================
p549.py
======================
import sys
from collections import defaultdict


def solve_dumbbell_sets_corrected(k, dumbbells):
    massToCosts = defaultdict(list)

    for m, c in dumbbells:
        massToCosts[m].append(c)

    frequency = []

    for mass, costs in massToCosts.items():
        costs.sort(reverse=True)
        frequency.append((len(costs), mass))

    frequency.sort(reverse=True, key=lambda x: x[0])

    # Check if we have enough masses with at least C dumbbells
    if len(frequency) < k:
        return 0, 0

    C = frequency[min(k, len(frequency)) - 1][0]

    selectedMasses = []
    for count, mass in frequency:
        if count < C:
            break

        costs = massToCosts[mass]
        sumCosts = sum(costs[:C])
        selectedMasses.append(sumCosts)

    selectedMasses.sort(reverse=True)

    totalCost = sum(selectedMasses[:k])

    return C, totalCost


input_data = sys.stdin.read().splitlines()
n, k = map(int, input_data[0].split())
dumbbells = [tuple(map(int, line.split())) for line in input_data[1:]]

result = solve_dumbbell_sets_corrected(k, dumbbells)

print(result[0], result[1])

=================
statement.txt
======================
549. Dumbbells
Time limit per test: 1 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



A sports shop has n dumbbells in store. Each of them is characterised by its mass mi and cost ci. Recently the shop manager faced the following non-trivial problem. He has to find the maximum number of sports sets that satisfy the following requirements:

each set must contain exactly k dumbbells;
each set must have dumbbells of k distinct masses;
for each pair of sets the masses of dumbbells must coincide , that is, the masses in the sets must be equal as .


The manager's task is to make the maximum number of such sets. If there are several ways to make the maximum possible number of sets, he should choose the one that has the maximum total cost of dumbbells that are contained in the chosen sets. Note that the primary goal is to maximize the number of sets and maximization of the total cost is the secondary goal.

Input
The first line of the input contains integers n and k (1 ≤ n,k ≤ 4000). Next n lines contain descriptions of the dumbbells, one per line. Each description consists of a pair of integers mi, ci (1 ≤ mi,ci ≤ 4000), mi is the mass of the i-th dumbbell, and ci is its cost.

Output
In the only output line print two integers — t and s, where t is the maximum number of sets, and s is the maximum total cost of dumbbells in t choosen sets. If the manager can't make at least one set, print a pair of zeroes.

Example(s)
sample input
sample output
7 2
16 1
4 6
16 7
7 100
32 9
4 6
32 1
2 22

sample input
sample output
4 2
1 2
2 1
4 3
1 7
1 10



Note
In the first sample the manager should make two sets. One of the possible solutions is as follows: the first set contains the second and the seventh dumbbells, the second set contains the fifth and the sixth dumbbells.

In the second sample the manager can make only one set. It consists of the third and the fourth dumbbells.


=================
