说明

时间限制：1 Sec 内存限制：256 MB 输入文件：bamboo.in 输出文件：bamboo.out

【定义】

一个三元组 $(a,b,c)$ 是凹凸三元组，如果 $a,b,c$ 两两不等并且 $b$ 是最大的或是最小的。

给定一个数列 $A_1,A_2,...,A_n$，它被称为凹凸数列列当且仅当对于每个 $2 \le i \le N-1$ 满足 $(A_{i-1},A_i,A_{i+1})$ 是凹凸三元组。

【问题】

超市售卖 $N$ 种竹子。第 $i$ 种竹子的长度为 $L_i$ 米，售价为 $W_i$ 元。

每种竹子的库存都十分充足，只要预算足够，你可以购买任意数量。

小明打算购买若干根竹子，将它们排成一列，使竹的长度序列满足凹凸数列的要求。

竹子不允许剩余、截断、拼接或拉长。

请你计算，在不超过 $C$ 元现金的前提下，能组成的门松列的竹子长度总和的最大值。

无需将现金全部用完。

输入格式

第一行两个整数 $N$ 和 $C$。

第二行 $N$ 个整数 $L_1,L_2,\cdots,L_N$。

第三行 $N$ 个整数 $W_1,W_2,\cdots,W_N$。

输出格式

输出满足条件的凹凸数列的竹子长度总和的最大值。

若无法组成任何凹凸数列，则输出 $0$。

样例

样例 1

4 10
9 4 3 2
5 3 1 3

17

样例说明：

- 购买 $2$ 根长度 $9$ 米、售价 $5$ 元的竹子，虽然长度总和最大，但无法组成凹凸数列。

- 购买 $1$ 根 $9$ 米/$5$ 元、$1$ 根 $3$ 米/$1$ 元、$2$ 根 $2$ 米/$3$ 元的竹子，可以组成凹凸数列 $(3,9,2,3)$，总长度为 $17$。

- 购买 $1$ 根 $9$ 米/$5$ 元、$1$ 根 $4$ 米/$3$ 元、$1$ 根 $3$ 米/$1$ 元的竹子，也能组成凹凸数列 $(9,3,4)$，但并非最优解。

样例 2

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

0

样例说明：

即使有若干根长度相同的竹子，也凹凸数列。

样例 3

4 11
1 2 3 4
1 1 1 1

30

样例说明：

可组成凹凸数列 $(3,4,2,3,1,4,2,3,1,4,3)$。

数据范围

对于 32% 的数据，$N \le 5$，$C \le 10$，$L_i,W_i \le 5$。

对于 100% 的数据，$1 \le N \le 50$，$1 \le C \le 50$，$1 \le L_i \le 50$，$1 \le W_i \le 50$。