定義

3つの要素から成る数列$v=(a_1,a_2,a_3)$が次の条件を満たす時，$v$は門松列であると言い伝えられています．

1. $a_1,a_2,a_3$は全て異なる
2. 3つの要素のうち$a_2$が最も大きい，あるいは最も小さい

さらに，$n$個の要素(ただし$3\le n$)から成る数列$w=(a_1,...,a_n)$が
どの連続した3つの要素を取り出しても門松列であるとき $w$は門松列列であると言います．

問題文

ユキコダホームセンターでは $N$ 種類の竹が売られています．
$i$ 本目の竹は長さ $L_i$ メートルで，価格は $W_i$ 円です．
どの竹も在庫は豊富にあるので，財布の許す限り何個でも買うことができます．

雪古寺さんは，幾つかの竹を購入して，竹の長さが門松列列になるように１列に並べたい．
竹は余らせたり切ったり繋げたり伸ばしたりしないものとします．

所持金 $C$ 円の制約の元で，門松列列の竹の長さの総和を最大化したとき，
作ることが出来る門松列列の竹の長さの総和を求めてください．
所持金を使い切る必要はありません．

入力

$N$ $C$
$L_1$ $\dots$ $L_N$
$W_1$ $\dots$ $W_N$

$1\le N\le 50$
$1\le C\le 50$
$1\le L_i\le 50$
$1\le W_i\le 50$
全て整数である．

最後に改行してください。

出力

問題文の制約を満たす門松列列の竹の長さの総和を出力してください．
1つも作れない場合は0を出力します．

サンプル

4 10
9 4 3 2
5 3 1 3

17

5 30
2 2 2 2 2
1 3 5 7 9

0

4 11
1 2 3 4
1 1 1 1

30