Codeforces Round 683 (Div. 2, by Meet IT)
C
Knapsack
Codeforces
未评级
原题
← BD →
翻译中…

You have a knapsack with the capacity of $W$. There are also $n$ items, the $i$-th one has weight $w_i$.

翻译中…

You want to put some of these items into the knapsack in such a way that their total weight $C$ is at least half of its size, but (obviously) does not exceed it. Formally, $C$ should satisfy: $\lceil \frac{W}{2}\rceil \le C \le W$.

翻译中…

Output the list of items you will put into the knapsack or determine that fulfilling the conditions is impossible.

翻译中…

If there are several possible lists of items satisfying the conditions, you can output any. Note that you don't have to maximize the sum of weights of items in the knapsack.

翻译中…

Input

翻译中…

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). Description of the test cases follows.

翻译中…

The first line of each test case contains integers $n$ and $W$ ($1 \le n \le 200\,000$, $1\le W \le 10^{18}$).

翻译中…

The second line of each test case contains $n$ integers $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 10^9$) — weights of the items.

翻译中…

The sum of $n$ over all test cases does not exceed $200\,000$.

翻译中…

Output

翻译中…

For each test case, if there is no solution, print a single integer $-1$.

翻译中…

If there exists a solution consisting of $m$ items, print $m$ in the first line of the output and $m$ integers $j_1$, $j_2$, ..., $j_m$ ($1 \le j_i \le n$, all $j_i$ are distinct) in the second line of the output  — indices of the items you would like to pack into the knapsack.

翻译中…

If there are several possible lists of items satisfying the conditions, you can output any. Note that you don't have to maximize the sum of weights items in the knapsack.

翻译中…

Note

翻译中…

In the first test case, you can take the item of weight $3$ and fill the knapsack just right.

翻译中…

In the second test case, all the items are larger than the knapsack's capacity. Therefore, the answer is $-1$.

翻译中…

In the third test case, you fill the knapsack exactly in half.

翻译中…

样例

Input #1
3
1 3
3
6 2
19 8 19 69 9 4
7 12
1 1 1 17 1 1 1
Output #1
1
1
-1
6
1 2 3 5 6 7
InputCopy OutputCopy
题目信息
题号
1447C
时间限制
2 s
内存限制
256 MB

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。