该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

机器人古章喜欢玩戮杀塔尖。

这一天，机器人古章在游戏中获得了超级遗物——超级送货员。超级送货员的效果是，如果你在商店中购买了一张卡牌，那么他会立刻补货和你刚刚购买的卡牌相同的卡牌，但是，超级送货员对卡牌的补货次数有限制，具体与卡牌的稀有度有关。请注意，这里超级送货员的效果与原游戏送货员的效果并不相同。

正巧，机器人古章将要走的下一个节点就是商店。商店中共售卖 $n$ 张卡牌，这些卡牌按顺序排成一排（与原游戏并不相同），其中购买第 $i$ 张卡牌需要花费 $a_i$ 枚金币，但会使机器人古章增加 $b_i$ 点启动速度。由于超级送货员的存在，机器人古章可以购买某张卡牌多次，但不能无限购买，根据第 $i$ 张卡牌的稀有度，第 $i$ 张卡牌可以被购买 $c_i$ 次（算上第一次购买），相同的卡牌的效果可以叠加。

机器人古章有一个特殊的习惯：他不会购买相邻的卡牌。若机器人古章购买了第 $i$ 张卡牌，那么他不会购买第 $(i-1)$ 张和第 $(i+1)$ 张卡牌（若这些卡牌存在）。

由于机器人古章忙着启动，他想问问你，在他初始拥有 $m$ 枚金币的情况下，他最大能增加多少点启动速度？

输入格式

输入第一行两个整数 $n$ , $m$ ,含义见题意。 $(1 \leq n \leq 10^3,1 \leq m \leq 10^4)$

输入第二行 $n$ 个整数 $a_i$ ,含义见题意。 $(1 \leq a_i \leq 10^4)$

输入第三行 $n$ 个整数 $b_i$ ,含义见题意。 $(1 \leq b_i \leq 10^9)$

输入第四行 $n$ 个整数 $c_i$ ,含义见题意。 $(1 \leq c_i \leq 10^4)$

输出格式

输出一行一个整数，表示答案。

输入输出样例

输入 #1

5 13
2 11 4 5 3
1 14 5 7 4
4 10 2 1 2

输出 #1

15

说明与提示

对于样例 #1:

购买一次第 $1$ 张卡牌，购买两次第 $3$ 张卡牌，购买一次第 $5$ 张卡牌是最优的，可以增加 $1+5\times2+4=15$ 点启动速度。