B. Ключ от сейфа
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Центральном банке Берляндии клиенты хранят свои деньги и ценности в ячейках в большом сейфе. Чтобы войти в сейф, клиент набирает личный секретный код, который представляет собой $$$n$$$ последовательных неотрицательных целых чисел.

В банке очень серьезно относятся к безопасности денег и ценностей, поэтому хотят, чтобы клиенты регулярно меняли код. Некоторые клиенты не очень любят менять код, потому что они постоянно его забывают. Забывчивые клиенты делают минимальные изменения в старом коде, чтобы получить новый. Чтобы бороться с таким поведением клиентов, банк сделал платной услугу оставить позицию кода без изменений.

У Родиона, постоянного клиента банка, истекает действие его секретного кода $$$A=[a_1, a_2, \ldots, a_n]$$$. Он придумал новый секретный код $$$B=[b_1, b_2, \ldots, b_n]$$$. Услуга изменения секретного кода в банке выглядит так: чтобы Родиону преобразовать старый код $$$A$$$ в новый $$$B$$$, он произвольное число раз может выполнить следующую операцию.

Выбрать целое число $$$k$$$ ($$$0 \le k \lt 40$$$). Для каждого элемента текущего кода $$$A$$$ выбирается одно из двух действий:

  • бесплатно заменить $$$a_i$$$ на $$$a_i \bmod 2^k$$$;
  • оставить $$$a_i$$$ без изменений и заплатить $$$2^k$$$ монет.

Стоимость операции равна сумме монет, заплаченных за все элементы, оставленные без изменений в этой операции.

Конечно, Родиону хочется заплатить за изменение кода поменьше. Помогите ему найти минимальную суммарную стоимость операций, после которых старый код $$$A$$$ станет равен новому коду $$$B$$$.

Если преобразовать код $$$A$$$ в код $$$B$$$ невозможно, выведите $$$-1$$$.

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

Тест содержит один или несколько наборов входных данных. В первой строке дано целое число $$$t$$$ — количество наборов входных данных ($$$1 \le t \le 1000$$$). Далее следуют описания наборов входных данных.

В первой строке каждого набора дано целое число $$$n$$$ — длина кода ($$$1 \le n \le 2 \cdot 10^5$$$).

Во второй строке даны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$, а в третьей строке — $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le a_i, b_i \lt 2^{40}$$$).

Сумма значений $$$n$$$ по всем наборам входных данных в одном тесте не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
4
2
1 7
0 1
3
3 1 4
1 5 9
4
13 10 4 4
1 2 4 4
2
1099511627775 549755813888
7 549755813888
Выходные данные
1
-1
6
8
Примечание

В первом примере можно выполнить следующие операции:

  1. Выбрать $$$k = 2$$$: заменить $$$a_1 = 1$$$ на $$$a_1 \bmod 2^2 = 1$$$ и $$$a_2 = 7$$$ на $$$a_2 \bmod 2^2 = 1$$$, после чего код принимает вид $$$A = [1, 1]$$$. Эта операция бесплатна.
  2. Выбрать $$$k = 0$$$: заменить $$$a_1 = 1$$$ на $$$a_1 \bmod 2^0 = 0$$$, а $$$a_2 = 1$$$ оставить без изменений и заплатить $$$2^0 = 1$$$ монету. Стоимость этой операции равна $$$1$$$. После этой операции код $$$A = [0, 1]$$$.

Итоговая суммарная стоимость равна $$$1$$$. Не существует последовательности операций меньшей стоимости, после которой код $$$A$$$ станет равен коду $$$B$$$.

Во втором примере выполнить требуемое преобразование невозможно.