Description

小朋友到商场去购物，商场里面的东西太多了，看的小朋友们眼花缭乱。小朋友拿着 m 元钱，准备去购物，商场里有 n 件物品，在小朋友的心目中，每个商品都有一定的价值，比如说书的价值是 10，游戏机的价值是 5，这说明在这个小朋友的心目中学习比玩游戏更重要，是一个爱学习的好孩子 (嘻嘻)。 为了方便购物，小朋友们把所有商品的价格分成了 3 类，第 1 类商品每个价格是 1，第 2 类商品每个的价格是 2，第 3 类商品每个的价格是 3。第 i 个商品的价格是 wi(1 ≤ wi ≤ 3)，价值是 vi。 很明显，小朋友希望用不超过 m 元钱买商品，并且要使得买到的商品的价值总和最大。现在，请你来帮助这个小朋友计算这个问题吧。

Input

输入的第一行是 2 个正整数 n 和 m，表示商品的总数和小朋友有的钱。 接下来一行有 n 个正整数 wi，分别表示每个商品的价格。 接下来一行有 n 个正整数 vi，分别表示每个商品在小朋友心目中的价值。

Output

输出可以买到的商品的最大价值总和。

Samples

3 3
1 2 2
1 2 3

4

5 7
3 2 1 2 1
2 2 1 3 1

7

16 24
1 1 1 1 2 3 1 2 3 3 2 2 3 3 2 3
5 2 5 3 4 10 1 9 6 1 8 5 7 7 6 8

75

Limitation

【样例1解释】 这里我们可以选择第 1 件和第 3 件商品，总的价值是 4。

【样例2解释】 选择第 1，3，4 和 5 个商品，也可以选择第 2，3，4 和 5 个物品

【数据范围】 对于所有的数据，保证 1 ≤ n ≤ 10^5，1 ≤ m ≤ 3×10^5，1 ≤ wi ≤ 3，1 ≤ vi ≤ 10^6。 .