C. Мистер совершенство
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Виктор хочет стать «Мистером совершенство». Для этого ему нужно овладеть определенным набором навыков. Более точно, у него есть $$$2$$$ навыка, которые ему нужно овладеть.

У него также есть $$$n$$$ книг. Чтение книги $$$i$$$ занимает у него $$$m_i$$$ минут и дает ему некоторые (возможно, ни одного) из двух необходимых навыков, представленных двоичной строкой длины $$$2$$$.

Какое минимальное количество времени потребуется, чтобы Виктор овладел обоими необходимыми навыками?

Входные данные

Входные данные состоят из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов случаев. Затем следует описание наборов.

Первая строка каждого набора содержит целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — количество доступных книг.

Затем следуют $$$n$$$ строк. Строка $$$i$$$ содержит положительное целое число $$$m_i$$$ ($$$1 \leq m_i \leq 2 \cdot 10^5$$$) и двоичную строку длины $$$2$$$, где $$$s_{i1} = 1$$$, если чтение книги $$$i$$$ дает Виктору навык $$$1$$$, и $$$s_{i1} = 0$$$ в противном случае, а $$$s_{i2} = 1$$$, если чтение книги $$$i$$$ дает Виктору навык $$$2$$$, и $$$s_{i2} = 0$$$ в противном случае.

Гарантируется, что сумма $$$n$$$ по всем тестовым случаям не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число, обозначающее минимальное количество минут, необходимое для того, чтобы Виктор овладел обоими необходимыми навыками, и $$$-1$$$, если невозможно овладеть двумя навыками после чтения любого количества книг.

Пример
Входные данные
6
4
2 00
3 10
4 01
4 00
5
3 01
3 01
5 01
2 10
9 10
1
5 11
3
9 11
8 01
7 10
6
4 01
6 01
7 01
8 00
9 01
1 00
4
8 00
9 10
9 11
8 11
Выходные данные
7
5
5
9
-1
8
Примечание

В первом тестовом случае мы можем использовать книги $$$2$$$ и $$$3$$$, с общим количеством потраченного времени, равным $$$3 + 4 = 7$$$.

Во втором тестовом случае мы можем использовать книги $$$1$$$ и $$$4$$$, с общим количеством потраченного времени, равным $$$3 + 2 = 5$$$.

В третьем тестовом случае у нас есть только один вариант, и это чтение книги $$$1$$$ за общее количество потраченного времени, равное $$$5$$$.