Xor Mart

問題

fine君は日常的に排他的論理和を使うことで有名な「XORマート」というお店にお買い物に来ました。

このお店には $N$ 個の商品があり、それぞれ $1$ から $N$ まで番号が振られています。そして、商品 $i$ の値段は $a_i$ 円であり、fine君が商品 $i$ を購入すると $b_i$ の満足度が得られます。

このとき、fine君が以下の条件を満たすように買い物をした場合に得られる満足度の最大値を求めてください。

• $0$ 個以上の商品を購入する
• 支払う金額が $M$ 円以下となる

ただし、XORマートでは日常的に排他的論理和を使うため、 $K$ 個の異なる商品 $i_1 , i_2 , \cdots , i_K$ を購入したときに支払う金額 $A$ は、排他的論理和の演算 $\oplus$ を用いて、 $A = a_{i_1} \oplus a_{i_2} \oplus \cdots \oplus a_{i_K}$と計算されます。

一方で、 $K$ 個の異なる商品 $i_1 , i_2 , \cdots , i_K$ を購入したときに得られる満足度 $B$ は、 $B = b_{i_1} + b_{i_2} + \cdots + b_{i_K}$と計算されることに注意してください。

制約

• $1 \leq N \leq 34$
• $0 \leq M \leq 10^9$
• $1 \leq a_i \leq 10^9$ ($1 \leq i \leq N$)
• $|b_i| \leq 10^9$ ($1 \leq i \leq N$)
• 入力は全て整数

入力

$N$ $M$
$a_1$ $a_2$ $\cdots$ $a_N$
$b_1$ $b_2$ $\cdots$ $b_N$

出力

適切に買い物をしたときに得られる満足度の最大値を出力してください。

入力例 1

4 3
1 3 4 5
2 5 -3 100

出力例 1

104

商品を全て買うのが最適な買い物となります。

商品 $3$ を買うと満足度が下がってしまいますが、 支払う金額を排他的論理和により計算しているため、商品 $3$ を除く全ての商品を買った場合と比べて支払う金額が少なくなります。

例えば、商品 $3$ を除く全ての商品を買った場合、満足度は最大となるものの支払う金額が $7$ 円となり条件を満たしません。一方、商品 $3$ を含む全ての商品を買うことで支払う金額をちょうど $3$ 円にすることができます。

入力例 2

1 1000000000
1
-1000000000

出力例 2

0

何も買わないのが最適な買い物となります。このとき、支払う金額は $0$ 円で得られる満足度は $0$ です。

入力例 3

4 8
1 2 4 8
13 6 32 50

出力例 3

51

---