407322: GYM102760 H Mock Competition Marketing

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

Whenever the application has available space for ads, the app requests the AdExchange platform to determine which ad to show. Then, the AdExchange holds an auction, in which bidders like MOLOCO bid for the opportunity to show their advertisement.

RUN wants to advertise its 2020 ICPC Mock Competition. They have asked MOLOCO for the advertisement. RUN has a total of $$$K$$$ dollars and wants to display the ad for internal apps used by KAISTians. 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 will run 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 will bid 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 for that auction is in RUN's set, and RUN has enough money to bid on an ad of that type, MOLOCO will submit a bid. Otherwise, they will ignore it.

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

The first line contains two space-separated integers $$$N$$$, $$$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$$$ indicates 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$$$ indicates the ad type of the $$$i$$$-th auction. ($$$1 \le c_i \le 6$$$)

Print the maximum number of ads they can bid on.

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

4

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

7

For both samples, it is optimal for RUN to select the set $$$\{1, 2, 3, 4\}$$$.