В Челябинской области есть небольшое село Берлин, в котором расположено $$$n$$$ домов, каждый из которых окружён забором. Глава Берлина решил улучшить облик села и покрасить заборы домов, на которых облупилась краска.
Дома пронумерованы целыми числами от $$$1$$$ до $$$n$$$, и за домом с номером $$$i$$$ идёт дом с номером $$$i+1$$$ для каждого $$$1 \leq i < n$$$. Для каждого дома $$$i$$$ известно целое значение $$$a_i$$$ от нуля до единицы:
Однако покраска выполняется особым образом: за один раз можно нанять бригаду из $$$k$$$ человек, которая способна покрасить любой подотрезок заборов длины $$$k$$$ за стоимость $$$cost_k$$$. Но бригада будет красить подотрезок заборов только в том случае, если хотя бы один из заборов на этом подотрезке домов уже покрашен. При этом любую бригаду можно нанять неограниченное число раз — в том числе ноль.
Более формально — если мы нанимаем бригаду размера $$$k$$$, то выбирается номер дома $$$i$$$ такой, что:
После этого красятся все заборы для домов с номерами $$$i, i + 1, \ldots, i + k - 1$$$.
Глава села хочет потратить как можно меньше денег, поэтому просит вас по заданным входным данным найти минимальную суммарную стоимость, чтобы покрасить все заборы.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует их описание.
В первой строке каждого набора входных данных содержится одно целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — количество домов в Берлине.
Во второй строке каждого набора входных данных содержится $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 1$$$), где $$$a_i$$$ обозначает состояние забора у дома с номером $$$i$$$.
В третьей строке каждого набора входных данных содержится $$$n$$$ целых чисел $$$cost_1, cost_2, \ldots, cost_n$$$ ($$$1 \leq cost_i \leq 100$$$), где $$$cost_i$$$ — стоимость покраски подотрезка домов длины $$$i$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$. Также гарантируется, что в каждом наборе входных данных есть хотя бы один покрашенный забор.
Для каждого набора выходных данных в единственной строке выведите минимальную стоимость покраски всех заборов.
611131 0 13 2 170 0 0 1 0 0 02 28 1 76 69 13 7721 099 5230 0 12 1 380 0 0 1 0 0 0 12 2 2 3 3 3 100 100
0135225
В первом наборе входных данных все заборы уже покрашены, поэтому ответ будет равен нулю.
Во втором наборе входных данных можно нанять бригаду из трёх человек, выбрав $$$i = 1$$$.
В третьем наборе входных данных можно трижды нанять бригаду из трёх человек: сначала выбрав $$$i = 3$$$, затем $$$i = 1$$$, и в конце выбрав $$$i = 5$$$.
В пятом наборе входных данных можно дважды нанять бригаду из двух человек: сначала выбрав $$$i = 2$$$, а затем выбрав $$$i = 1$$$.