問題文

フィボナッチ数 $F_n$ を、次の漸化式で定義される数列とします。 $$F_n = \begin{cases} 1 & n = 1 \\ 2 & n = 2 \\ F_{n - 2} + F_{n - 1} & n \ge 3 \end{cases}$$

$N$ 個の品物があります。品物には $1, 2, \ldots, N$ と番号が振られています。各 $i = 1, 2, \ldots, N$ について、品物 $i$ の重さは $w_i$ で、価値は $F_{i}$ です。

まぐふらい君は、これらの品物をスーツケースに詰めて運ぼうとしています。ただし、スーツケースに詰める重さの総和は $W$ 以下である必要があります。

スーツケースに詰める品物の、価値の総和の最大値を求めてください（ただし、スーツケースに詰められる品物が存在しない場合は $0$ としてください）。なお、この問題の制約下で、価値の総和は $10^{18}$ を超えないことが証明できます。

$T$ 個のテストケースについて求めてください。

入力

$T$
$case_1$
$case_2$
$\vdots$
$case_{T}$

$N$ $W$
$w_1$ $w_2$ $\dots$ $w_N$

• $1 \le T \le 100$
• $1 \le N \le 75$
• $1 \le W \le 10^{18}$
• $1 \le w_i \le 10^{16}$
• 与えられる入力はすべて整数

出力

$T$ 行出力してください。$i$ 行目には $i$ 番目のテストケースの答えを出力して下さい。

サンプル

1
5 7
1 2 3 4 5

10

1
5 7
8 9 10 11 12

0

2
11 50
1 3 3 3 12 129 13 34 68 30 24
20 6023
286 1304 1882 1144 6 1154 642 136 1076 1638 968 1266 448 374 288 1298 1708 1344 580 1088

176
26492