Description

Given a non-negative integer $x$, you need to transform it into $y$ through a series of operations with the minimum cost. Each operation is defined as follows:

• Choose an integer $0 \leq i \leq k$, and pay a cost of $a_i$ to either add or subtract $2^i$ from $x$.

Note: You do not need to ensure that $x$ remains non-negative during the operations.

Input Format

For each test case, output a single non-negative integer—the minimum cost required to transform $x$ into $y$.

Output Format

For each test case, output a single non-negative integer—the minimum cost required to transform $x$ into $y$.

5
2 4 1
2 5
2 5 2
2 5 2
3 9 2
1 2 3
4 23 3
1 5 2 4
1 114 5
1 4 1 9 19 8

4
4
5
11
29

Hint

Sample Explanation

For the second test case in the sample input, the following two operations transform $x$ into $y$ with the minimum cost:

1. Choose $i=2$, perform $x \gets x + 2^2$, resulting in $x=6$ with a cost of $2$.
2. Choose $i=0$, perform $x \gets x - 2^0$, resulting in $x=5$ with an additional cost of $2$, totaling $4$.

Data Range

This problem uses bundled testing.

For all test cases:

• $1 \leq T \leq 2 \times 10^5$,
• $0 \leq x, y < 2^{30}$,
• $1 \leq k \leq 30$,
• $1 \leq a_i \leq 10^9$.

Hint

Please use fast input methods for reading data.

Translated by DeepSeek V3.