CF1183G.Candy Box (hard version)

This problem is a version of problem D from the same contest with some additional constraints and tasks.

There are $n$ candies in a candy box. The type of the $i$-th candy is $a_i$ ($1 \le a_i \le n$).

You have to prepare a gift using some of these candies with the following restriction: the numbers of candies of each type presented in a gift should be all distinct (i. e. for example, a gift having two candies of type $1$ and two candies of type $2$ is bad).

It is possible that multiple types of candies are completely absent from the gift. It is also possible that not all candies of some types will be taken to a gift.

You really like some of the candies and don't want to include them into the gift, but you want to eat them yourself instead. For each candy, a number $f_i$ is given, which is equal to $0$ if you really want to keep $i$-th candy for yourself, or $1$ if you don't mind including it into your gift. It is possible that two candies of the same type have different values of $f_i$.

You want your gift to be as large as possible, but you don't want to include too many of the candies you want to eat into the gift. So, you want to calculate the maximum possible number of candies that can be included into a gift, and among all ways to choose maximum number of candies, you want to maximize the number of candies having $f_i = 1$ in your gift.

You have to answer $q$ independent queries.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.

本题是同一场竞赛中问题 D 的一个变体，附加了一些额外的约束和任务。

糖果盒中有 $n$ 颗糖果。第 $i$ 颗糖果的类型为 $a_i$（$1 \le a_i \le n$）。

你需要用其中一部分糖果准备一份礼物，且需满足如下限制：礼物中每种类型的糖果数量必须互不相同（例如，礼物中包含两颗类型 $1$ 的糖果和两颗类型 $2$ 的糖果，这是不允许的）。

礼物中可以完全不包含某些类型的糖果；对于某些类型，也可以只取其中的一部分糖果，而非全部。

你特别喜欢其中一些糖果，不希望将它们放入礼物中，而想留给自己吃。对每颗糖果，给定一个数 $f_i$：若 $f_i = 0$，表示你强烈希望将第 $i$ 颗糖果留给自己；若 $f_i = 1$，则表示你并不介意将其放入礼物中。注意，同一种类型的两颗糖果可能具有不同的 $f_i$ 值。

你希望礼物中的糖果总数尽可能多；但同时，你又不希望把太多你想自己吃的糖果（即 $f_i = 0$ 的糖果）放进礼物里。因此，你需要先计算出礼物中最多能包含多少颗糖果；在所有能达到该最大糖果数的方案中，再最大化礼物中满足 $f_i = 1$ 的糖果数量。

你需要回答 $q$ 个相互独立的查询。

如果你使用 Python 编程，请在提交代码时考虑使用 PyPy 而非 Python。

The first line of the input contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries.

The first line of each query contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of candies.

Then $n$ lines follow, each containing two integers $a_i$ and $f_i$ ($1 \le a_i \le n$, $0 \le f_i \le 1$), where $a_i$ is the type of the $i$-th candy, and $f_i$ denotes whether you want to keep the $i$-th candy for yourself ($0$ if you want to keep it, $1$ if you don't mind giving it away).

It is guaranteed that the sum of $n$ over all queries does not exceed $2 \cdot 10^5$.

输入的第一行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$），表示查询次数。

每个查询的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示糖果的数量。

接下来是 $n$ 行，每行包含两个整数 $a_i$ 和 $f_i$（$1 \le a_i \le n$，$0 \le f_i \le 1$），其中 $a_i$ 表示第 $i$ 颗糖果的类型，$f_i$ 表示你是否愿意将第 $i$ 颗糖果留给自己（$0$ 表示你想保留它，$1$ 表示你不介意将其送人）。

保证所有查询的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each query print two integers:

• the maximum number of candies in a gift you can compose, according to the constraints in the statement;
• the maximum number of candies having $f_i = 1$ in a gift you can compose that contains the maximum possible number of candies.

对于每个查询，请输出两个整数：

• 根据题目约束条件，你能组成的礼物中糖果的最大数量；
• 在包含最多可能数量糖果的礼物中，满足 $f_i = 1$ 的糖果的最大数量。

In the first query, you can include two candies of type $4$ and one candy of type $5$. All of them have $f_i = 1$ and you don't mind giving them away as part of the gift.

在第一次查询中，你可以包含两颗类型为 $4$ 的糖果和一颗类型为 $5$ 的糖果。它们的 $f_i$ 均为 $1$，你并不介意将它们作为礼物送出。