Definition

It has been handed down that when a sequence $v = (a_1,a_2,a_3)$ consisting of 3 elements satisfies the following conditions, $v$ is a Kadomatsu sequence.

1. $a_1,a_2,a_3$ are all distinct
2. Among the 3 elements, $a_2$ is the largest or the smallest

Furthermore, for a sequence $w = (a_1,...,a_n)$ consisting of $n$ elements (where $3\le n$),
if any 3 consecutive elements taken from it form a Kadomatsu sequence, $w$ is called a Kadomatsu sequence sequence.

Problem Statement

Yukikoda Home Center sells $N$ types of bamboo.
The $i$-th bamboo is $L_i$ meters long and costs $W_i$ yen.
Every bamboo is amply stocked, so you can buy as many as your wallet allows.

Yukikoji-san wants to buy some bamboos and arrange them in a row so that their lengths form a Kadomatsu sequence sequence.
Bamboos must not be left over, cut, joined, or stretched.

Under the constraint of having $C$ yen, when the total length of the bamboos in the Kadomatsu sequence sequence is maximized,
find the total length of the bamboos in the Kadomatsu sequence sequence that can be made.
You do not need to use up all of your money.

Input

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

$1 \le N \le 50$
$1 \le C \le 50$
$1 \le L_i \le 50$
$1 \le W_i \le 50$
All values are integers.

Print a newline at the end.

Output

Output the total length of the bamboos in the Kadomatsu sequence sequence satisfying the constraints of the problem statement.
If none can be made, output 0.

Sample

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