MOLOCO 是一家利用其高性能广告平台将广告主与潜在用户进行匹配的公司。

每当应用程序有可用的广告位时，该应用就会请求 AdExchange 平台来决定展示哪条广告。然后，AdExchange 会举行一场竞拍，像 MOLOCO 这样的竞拍者会竞标展示其广告的机会。

RUN 想要为其 2020 ICPC 模拟赛做广告。他们委托 MOLOCO 进行广告投放。RUN 共有 $K$ 元预算，并希望在 KAIST 学生使用的内部应用中展示广告。这些应用中的广告共有六种类型之一，且竞拍价格仅取决于广告的类型。第一个对广告进行出价的竞拍者将获得展示其广告的机会。

AdExchange 已经确定了六种广告类型的成本以及今天将进行的 $N$ 场竞拍。在第 $i$ 场竞拍中，AdExchange 将对类型为 $c_i$ 的广告进行竞拍。AdExchange 从不同时进行两场竞拍，更具体地说，在第 $i$ 场竞拍结束之前，第 $i + 1$ 场竞拍不会开始。

MOLOCO 将在竞拍期间使用以下策略——在竞拍开始之前，RUN 选择一个广告类型集合。在第 $i$ 场竞拍期间，如果该场竞拍的广告类型在 RUN 选择的集合中，且 RUN 有足够的资金对该类型的广告进行出价，则 MOLOCO 将提交出价。否则，他们将忽略它。MOLOCO 的出价速度非常快，因此只要它出价，就总是能成为第一个出价者。确定如果 RUN 最优地选择广告类型集合，他们最多可以成功竞拍到多少个广告。

输入格式

第一行包含两个空格分隔的整数 $N, K$。($1 \le N \le 100\,000, 0 \le K \le 10^9$)

第二行包含 6 个整数 $b_1, b_2, \dots, b_6$。$b_i$ 表示广告类型 $i$ 的成本。($1 \le b_i \le 10^9$)

第三行包含 $N$ 个整数 $c_1, c_2, \dots, c_N$。$c_i$ 表示第 $i$ 场竞拍的广告类型。($1 \le c_i \le 6$)

输出格式

输出他们最多可以成功竞拍到的广告数量。

样例

输入样例 1

6 10
1 2 3 4 5 6
6 5 4 3 2 1

输出样例 1

4

输入样例 2

12 10
1 1 2 2 3 3
6 5 4 3 2 1 1 2 3 4 5 6

输出样例 2

7

说明

对于这两个样例，RUN 选择集合 $\{1, 2, 3, 4\}$ 是最优的。