该问题是同一竞赛中问题 D 的一个版本,带有一些额外的约束和任务。
糖果盒中有 $$$n$$$ 糖果。第 $$$i$$$ 糖果的类型为 $$$a_i$$$ ($$$1 \le a_i \le n$$$)。
您必须使用其中一些糖果来准备一份礼物,但有以下限制:礼物中每种类型的糖果数量应该完全不同(即,例如,包含两颗 $$$1$$$ 类型的糖果和两颗 $$$2$$$ 类型的糖果的礼物是不好的)。
礼物中可能完全没有多种类型的糖果。也有可能并非所有类型的糖果都会被当作礼物。
您确实很喜欢其中一些糖果,并且不想将它们包含在礼物中,但您想自己吃掉它们。对于每颗糖果,都会给出一个数字 $$$f_i$$$,如果您确实想为自己保留第 $$$i$$$ 颗糖果,则该数字等于 $$$0$$$;如果您不介意将其包含在礼物中,则等于 $$$1$$$。两种相同类型的糖果可能具有不同的 $$$f_i$$$ 值。
您希望您的礼物尽可能大,但又不想在礼物中包含太多您想吃的糖果。因此,您想要计算可以包含在礼物中的最大可能糖果数量,并且在选择最大糖果数量的所有方法中,您希望最大化礼物中具有 $$$f_i = 1$$$ 的糖果数量。
您必须回答 $$$q$$$ 独立查询。
如果您是 Python 程序员,请在提交代码时考虑使用 PyPy 而不是 Python。
输入
输入的第一行包含一个整数 $$$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$$$。
输出
对于每个查询打印两个整数:
- 根据声明中的限制,您可以制作的礼物中糖果的最大数量;
- 您可以制作的包含尽可能多糖果的礼物中,$$$f_i = 1$$$ 的糖果的最大数量。
示例
输入 #1
3 8 1 0 4 1 2 0 4 1 5 1 6 1 3 0 2 0 4 1 1 1 1 2 1 2 1 9 2 0 2 0 4 1 4 1 4 1 7 0 7 1 7 0 7 1
输出 #1
3 3 3 3 9 5
注意
在第一个查询中,您可以包含两颗 $$$4$$$ 类型的糖果和一颗 $$$5$$$ 类型的糖果。它们都有 $$$f_i = 1$$$ 并且您不介意将它们作为礼物的一部分赠送出去。