Mock Competition Marketing

MOLOCO is a company that matches advertisers with potential users through its high-performance ad platform.

Whenever an app has space available for an ad, the app asks the AdExchange platform to decide which ad to show. AdExchange then holds an auction, in which bidders such as MOLOCO bid for the chance to show their advertisement.

RUN wants to advertise its 2020 ICPC Mock Competition. They have asked MOLOCO to place the advertisement. RUN has a total of $K$ dollars and wants to display the ad in internal apps used by KAIST members. The ads in those apps are in one of six types, and the bidding price depends only on the type of ad. The first bidder to bid on the ad gets to show their ad.

AdExchange has already determined the costs of the six ad types and the $N$ auctions it will run today. In the $i$-th auction, AdExchange runs an auction for an ad of type $c_i$. AdExchange never runs two auctions at the same time; more specifically, auction $i+1$ cannot start until after auction $i$ ends.

MOLOCO bids during auctions using the following strategy. Before the auctions begin, RUN selects a set of ad types. During the $i$-th auction, if the ad type of that auction is in RUN's set and RUN has enough money to bid on an ad of that type, MOLOCO submits a bid. Otherwise, it ignores the auction.

MOLOCO is very fast at bidding, so it is always the first bidder if it bids on the ad. Find the maximum number of ads MOLOCO can bid on if RUN selects the set of ad types optimally.

The first line contains two space-separated integers $N$ and $K$. ($1 \le N \le 100\,000, 0 \le K \le 10^9$)

The next line contains 6 integers $b_1, b_2, \ldots, b_6$. $b_i$ is the cost for ad type $i$. ($1 \le b_i \le 10^9$)

The next line contains $N$ integers $c_1, c_2, \ldots, c_N$. $c_i$ is the ad type of the $i$-th auction. ($1 \le c_i \le 6$)

Print the maximum number of ads MOLOCO can bid on.