Distinct Elements with Minimum Total CostMedium

Distinct Elements with Minimum Total Cost

MediumPractice library · +20 XPheapshash setgreedy

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

Time limit 2 s (native code; slower languages get more)Memory 256 MB13 hidden tests

Example 1

Input
5 3
10 5
20 3
10 2
30 8
20 4
Output
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

Input
7 2
5 10
5 1
10 5
10 3
15 7
20 2
20 6
Output
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