모의 대회 광고

MOLOCO는 고성능 광고 플랫폼으로 광고주와 잠재 사용자를 연결하는 회사이다.

앱에 광고를 넣을 공간이 생기면, 앱은 어떤 광고를 보여줄지 결정하기 위해 AdExchange 플랫폼에 요청한다. 그러면 AdExchange는 경매를 열고, MOLOCO 같은 입찰자들이 자기 광고를 보여줄 기회를 두고 입찰한다.

RUN은 2020 ICPC 모의 대회를 광고하려고 한다. RUN은 MOLOCO에 광고를 의뢰했다. RUN은 총 $K$달러를 가지고 있고, KAIST 구성원이 쓰는 내부 앱에 광고를 보여주려고 한다. 그 앱의 광고는 여섯 가지 유형 중 하나이며, 입찰 가격은 광고 유형에만 따라 결정된다. 그 광고에 가장 먼저 입찰한 입찰자가 자기 광고를 보여줄 수 있다.

AdExchange는 여섯 광고 유형의 비용과 오늘 진행할 $N$번의 경매를 이미 정해 두었다. $i$번째 경매에서 AdExchange는 $c_i$ 유형의 광고를 두고 경매를 연다. AdExchange는 두 경매를 동시에 열지 않으며, 더 구체적으로 $i$번째 경매가 끝나기 전에는 $i+1$번째 경매를 시작할 수 없다.

MOLOCO는 다음과 같은 전략으로 경매에 참여한다. 경매가 시작되기 전에 RUN이 광고 유형 집합을 고른다. $i$번째 경매에서 그 경매의 광고 유형이 RUN이 고른 집합에 속하고 RUN이 그 유형의 광고에 입찰할 만큼 돈이 있으면, MOLOCO는 입찰한다. 그렇지 않으면 그냥 넘어간다.

MOLOCO는 입찰이 매우 빨라서, 입찰하면 항상 가장 먼저 입찰한 입찰자가 된다. RUN이 광고 유형 집합을 최적으로 고를 때 MOLOCO가 입찰할 수 있는 광고 수의 최댓값을 구하시오.

첫 번째 줄에 공백으로 구분된 두 정수 $N$, $K$가 주어진다. ($1 \le N \le 100\,000, 0 \le K \le 10^9$)

다음 줄에 6개의 정수 $b_1, b_2, \ldots, b_6$이 주어진다. $b_i$는 광고 유형 $i$의 비용이다. ($1 \le b_i \le 10^9$)

다음 줄에 $N$개의 정수 $c_1, c_2, \ldots, c_N$이 주어진다. $c_i$는 $i$번째 경매의 광고 유형이다. ($1 \le c_i \le 6$)

MOLOCO가 입찰할 수 있는 광고 수의 최댓값을 출력한다.