<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

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.

<|response|>
1. Abridged Problem Statement  
You have n dumbbells, each with a mass mᵢ and a cost cᵢ. You want to form as many identical “sets” as possible, where:  
- Each set contains exactly k dumbbells.  
- Within a set, all k masses must be distinct.  
- All sets use the same k masses.  
First maximize the number t of complete sets you can form. Then, among all ways to form t sets, maximize the total cost of the selected dumbbells. Output t and that maximum total cost. If you cannot form even one set, output “0 0.”

2. Key Observations  
- To make t sets you need k distinct masses, each available in at least t copies.  
- For a given mass m with c₁, c₂, …, cₚ costs sorted descending, if you use that mass in t sets you will pick its t most expensive dumbbells (c₁ + … + cₜ).  
- The maximum possible t is determined by the k-th largest supply among all masses.  
- Once t is fixed, among all masses with supply ≥ t, you should pick the k masses whose top-t sum of costs is largest.

3. Full Solution Approach  
Step 1. Group by mass  
- Build a map mass → list of costs.  

Step 2. Sort each group’s costs in descending order  
- This lets you quickly compute the sum of the top t costs for any t.  

Step 3. Gather supplies  
- For each mass m, let countₘ = number of dumbbells of that mass.  
- Form a list of these counts and sort it descending.  

Step 4. Determine t (maximum number of sets)  
- If there are fewer than k distinct masses, answer is (0,0).  
- Otherwise, the maximum t is the k-th largest count in the sorted list.  

Step 5. Maximize total cost for t sets  
- Among all masses with countₘ ≥ t, compute Sₘ = sum of the top t costs.  
- Sort the Sₘ values descending and take the sum of the top k of them.  

Step 6. Output  
- Print t and the computed total cost.  

Complexity:  
- Grouping and sorting costs in each group: O(n log n) total.  
- Sorting the counts: O(M log M), where M ≤ n is the number of distinct masses.  
- Summing top-t costs and sorting those sums: O(M log M).  
Fits easily for n,k ≤ 4000.

4. C++ Implementation with Detailed Comments  
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    int n, k;
    cin >> n >> k;

    // Step 1: collect costs by mass
    unordered_map<int, vector<int>> mass2costs;
    mass2costs.reserve(n);
    for (int i = 0; i < n; i++) {
        int m, c;
        cin >> m >> c;
        mass2costs[m].push_back(c);
    }

    // Step 2 & 3: sort each mass's costs descending; record (count, mass)
    vector<pair<int,int>> supply;  // (count of dumbbells, mass)
    supply.reserve(mass2costs.size());
    for (auto &entry : mass2costs) {
        int mass = entry.first;
        auto &costs = entry.second;
        sort(costs.begin(), costs.end(), greater<int>());
        supply.emplace_back((int)costs.size(), mass);
    }

    // Sort supplies by descending count
    sort(supply.begin(), supply.end(), greater<>());

    // If fewer than k distinct masses, we cannot form any set
    if ((int)supply.size() < k) {
        cout << "0 0\n";
        return 0;
    }

    // Step 4: t = k-th largest count
    int t = supply[k-1].first;
    if (t == 0) {
        // degenerate case, though supply.size() >= k implies t>0
        cout << "0 0\n";
        return 0;
    }

    // Step 5: For masses with count >= t, compute sum of top t costs
    vector<ll> candidates;
    candidates.reserve(supply.size());
    for (auto &p : supply) {
        int cnt = p.first;
        int mass = p.second;
        if (cnt < t) break;  // further ones have even fewer
        ll s = 0;
        auto &costs = mass2costs[mass];
        for (int i = 0; i < t; i++) {
            s += costs[i];
        }
        candidates.push_back(s);
    }

    // Choose the k largest sums
    sort(candidates.begin(), candidates.end(), greater<ll>());
    ll totalCost = 0;
    for (int i = 0; i < k; i++) {
        totalCost += candidates[i];
    }

    // Step 6: output result
    cout << t << " " << totalCost << "\n";
    return 0;
}
```

5. Python Implementation with Detailed Comments  
```python
import sys
from collections import defaultdict

def main():
    data = sys.stdin.read().split()
    n, k = map(int, data[:2])
    idx = 2

    # Step 1: group costs by mass
    mass_to_costs = defaultdict(list)
    for _ in range(n):
        m = int(data[idx]); c = int(data[idx+1])
        idx += 2
        mass_to_costs[m].append(c)

    # Step 2 & 3: sort each mass's costs descending; build supply list
    supply = []  # list of (count, mass)
    for m, costs in mass_to_costs.items():
        costs.sort(reverse=True)
        supply.append((len(costs), m))

    # Sort by descending count
    supply.sort(reverse=True)

    # If fewer than k distinct masses, no sets can be formed
    if len(supply) < k:
        print(0, 0)
        return

    # Step 4: maximum number of sets t = k-th largest count
    t = supply[k-1][0]
    if t == 0:
        print(0, 0)
        return

    # Step 5: compute for each mass with count>=t the sum of top t costs
    candidate_sums = []
    for cnt, m in supply:
        if cnt < t:
            break
        # sum the t largest costs
        candidate_sums.append(sum(mass_to_costs[m][:t]))

    # pick the best k sums
    candidate_sums.sort(reverse=True)
    total_cost = sum(candidate_sums[:k])

    # Step 6: output t and total cost
    print(t, total_cost)

if __name__ == "__main__":
    main()
```