В Центральном банке Берляндии клиенты хранят свои деньги и ценности в ячейках в большом сейфе. Чтобы войти в сейф, клиент набирает личный секретный код, который представляет собой $$$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$$$ станет равен новому коду $$$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$$$. Не существует последовательности операций меньшей стоимости, после которой код $$$A$$$ станет равен коду $$$B$$$.
Во втором примере выполнить требуемое преобразование невозможно.
| Название |
|---|


