Distinct Elements with Minimum Total Cost
You are given N integers, where the i-th integer is v_i and its associated cost is c_i. You want to select a subset of these integers such that there are exactly K distinct values among the selected integers. The cost of selecting an integer v_i with cost c_i is c_i. You want to minimize the total cost of selected integers to achieve K distinct values. If multiple sets of selections achieve K distinct values with the minimum total cost, choose the one that uses the smallest number of selected integers. If there is still a tie, choose the one that lexicographically smallest set of selected values (sorted in ascending order). Print the minimum total cost and the minimum number of elements selected for that cost.
Input
The first line contains two integers N and K. The next N lines each contain two integers v_i and c_i, separated by a space.
Output
Print two integers: the minimum total cost and the minimum number of elements selected for that cost.
Constraints
1 <= N <= 200000 1 <= K <= N 1 <= v_i <= 10^9 1 <= c_i <= 10^9
Example 1
5 3 10 5 20 3 10 2 30 8 20 4
13 3
Distinct values are 10 (min cost 2), 20 (min cost 3), 30 (min cost 8). To get 3 distinct values, we pick 10, 20, 30. Total cost = 2+3+8 = 13. Number of elements = 3.
Example 2
7 2 5 10 5 1 10 5 10 3 15 7 20 2 20 6
3 2
Distinct values are 5 (min cost 1), 10 (min cost 3), 15 (min cost 7), 20 (min cost 2). To get 2 distinct values with minimum cost, we pick 5 (cost 1) and 10 (cost 3). Total cost = 1+3 = 4. Number of elements = 2.
Hints
Similar problems
- Distinct Element Sum with Minimum CostMedium
- Maximize Distinct Elements After OperationsMedium
- Process Tasks by DeadlineMedium
- Minimize Maximum Difference of Elements in IntervalsHard
- Find K Distinct Element FrequenciesMedium
- Distinct Elements CountMedium
More topics: Hash Map and Hashing problems, Greedy problems, Heap and Priority Queue problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 3 10 5 20 3 10 2 30 8 20 4
7 2 5 10 5 1 10 5 10 3 15 7 20 2 20 6