E. Transition
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$t$$$ test cases. For each test case, you are given two integers $$$a$$$ and $$$b$$$ ($$$a \lt b$$$), and $$$n$$$ available operations.

The $$$i$$$-th operation is described by a pair $$$(x_i, y_i)$$$:

  • If $$$x_i = 1$$$, then applying this operation changes the current value $$$v$$$ to $$$v + 1$$$.
  • If $$$x_i = 2$$$, then applying this operation changes the current value $$$v$$$ to $$$2v$$$.
  • Applying operation $$$i$$$ costs $$$y_i$$$.

Initially, $$$v = a$$$.

You may apply each operation at most once, in any order. You may only apply an operation if after applying it the value does not exceed $$$b$$$ (i.e., you must keep $$$v \le b$$$ at all times).

Your task is to find the minimum total cost needed to reach exactly $$$v = b$$$. If it is impossible, output $$$-1$$$.

Input
  • The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
  • Each test case starts with a line containing three integers $$$n$$$, $$$a$$$, $$$b$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le a \lt b \le 10^9$$$).
  • The next line contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$x_i \in {1,2}$$$) — the types of the operations.
  • The next line contains $$$n$$$ integers $$$y_1, y_2, \dots, y_n$$$ ($$$0 \le y_i \le 10^9$$$) — the costs of the operations.
  • It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.
Output

For each test case, print one integer: the minimum total cost to reach $$$b$$$, or $$$-1$$$ if it is impossible.

Example
Input
2
4 3 10
2 1 1 1
2 5 1 1
2 1 5
2 2
3 4
Output
4
-1
Note

In the first test case, the cheapest way is to use two cheap $$$+1$$$ operations first, then double: $$$3 \to 4 \to 5 \to 10$$$, with total cost $$$1+1+2=4$$$.

In the second test case, only doubling operations are available, so from $$$1$$$ we can reach only $$$2$$$ and $$$4$$$, but never $$$5$$$. Hence the answers are $$$\texttt{4}$$$ and $$$\texttt{-1}$$$.