Full Enough (Hard Version) - Testing Approx Problems | Repovive

1012F. Full Enough (Hard Version)

1s256 MB

You are given $n$ stones. The weight of stone $i$ is $w_i$ .

You have a bag with capacity $W$ . You may choose any subset of stones whose total weight is at most $W$ .

The score of your choice is the total weight of the chosen stones.

Let $OPT$ be the maximum possible score.

You do not need to find an optimal subset. You only need to output any subset whose score is at least $90\%$ of $OPT$ .

In other words, if the score of your subset is $S$ , your output is accepted if $10 \times S \ge 9 \times OPT$ .

Constraints

$1 \le t \le 3$
$1 \le n \le 750$
$1 \le W \le 3 \times 10^7$
$1 \le w_i \le W$
The sum of $n$ over all test cases is at most $750$

Input

The input is given in the following format:

t

\left. \begin{array}{l} n \quad W \\ w_1 \quad w_2 \quad \cdots \quad w_n \end{array} \right\} \times t

Output

For each test case, first output an integer $k$ , the number of chosen stones.

Then output $k$ distinct integers $i_1, i_2, \ldots, i_k$ , the indices of the chosen stones.

The total weight of the chosen stones must not exceed $W$ .

If the score of your subset is $S$ , it must satisfy $10 \times S \ge 9 \times OPT$ .

The output format is:

\left. \begin{array}{l} k \\ i_1 \quad i_2 \quad \cdots \quad i_k \end{array} \right\} \times t

If $k=0$ , the second line for that test case should be empty.

Samples

Input

1
8 100
45 45 60 40 30 20 15 5

Explanation

The chosen stones have total weight $45+45=90$ .

This does not fill the bag exactly, but it is still valid because $90$ is exactly $90\%$ of $100$ and does not exceed the capacity.

Output

2
1 2

You are given $n$ stones. The weight of stone $i$ is $w_i$ .

You have a bag with capacity $W$ . You may choose any subset of stones whose total weight is at most $W$ .

The score of your choice is the total weight of the chosen stones.

Let $OPT$ be the maximum possible score.

You do not need to find an optimal subset. You only need to output any subset whose score is at least $90\%$ of $OPT$ .

In other words, if the score of your subset is $S$ , your output is accepted if $10 \times S \ge 9 \times OPT$ .

$1 \le t \le 3$
$1 \le n \le 750$
$1 \le W \le 3 \times 10^7$
$1 \le w_i \le W$
The sum of $n$ over all test cases is at most $750$

The input is given in the following format:

t

\left. \begin{array}{l} n \quad W \\ w_1 \quad w_2 \quad \cdots \quad w_n \end{array} \right\} \times t

For each test case, first output an integer $k$ , the number of chosen stones.

Then output $k$ distinct integers $i_1, i_2, \ldots, i_k$ , the indices of the chosen stones.

The total weight of the chosen stones must not exceed $W$ .

If the score of your subset is $S$ , it must satisfy $10 \times S \ge 9 \times OPT$ .

The output format is:

\left. \begin{array}{l} k \\ i_1 \quad i_2 \quad \cdots \quad i_k \end{array} \right\} \times t

If $k=0$ , the second line for that test case should be empty.

The chosen stones have total weight $45+45=90$ .

This does not fill the bag exactly, but it is still valid because $90$ is exactly $90\%$ of $100$ and does not exceed the capacity.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

1012F. Full Enough (Hard Version)

Constraints

Input

Output

Samples

1012F. Full Enough (Hard Version)

Constraints

Input

Output

Samples