Эта задача — усложненная версия задачи D из этого же самого контеста с дополнительными ограничениями и заданиями.
В коробке с конфетами находятся \(n\) конфет. Тип \(i\)-й конфеты равен \(a_i\) (\(1 \le a_i \le n\)).
Вы хотите приготовить подарок, используя некоторые из этих конфет, со следующим ограничением: количества конфет каждого типа, находящегося в подарке, должны быть различны (то есть, например, подарок, имеющий две конфеты типа \(1\) и две конфеты типа \(2\) является плохим).
Возможно, что некоторые типы конфет могут вообще не находиться в подарке. Также возможно, что не все конфеты каких-то типов будут взяты в подарок.
Вы очень любите некоторые конфеты из коробки и не хотите их включать в подарок (вы бы предпочли сами их съесть). Для каждой конфеты задано число \(f_i\), которое равно \(0\), если вы хотите оставить \(i\)-ю конфету себе, или \(1\), если вы вполне можете отдать ее, и это не вызовет у вас никаких отрицательных эмоций. Возможно, что у двух конфет одного типа могут быть разные значения \(f_i\).
Вы хотите собрать как можно больше конфет в подарок — но, с другой стороны, вы не хотите отдавать слишком много конфет из тех, которые бы предпочли съесть сами. Поэтому вы хотите посчитать максимальное число конфет, которое может быть включено в подарок, а среди всех способов выбрать максимальное число конфет в подарке — максимально возможное количество конфет с \(f_i = 1\).
Вам необходимо ответить на \(q\) независимых запросов.
Если Вы программируете на Python, рассмотрите возможность отправки решения на PyPy, а не на Python, когда будете отправлять свой код.