보충 수업 이용권 상담

문제

한 학원은 방학 동안 열리는 보충 수업의 이용권을 판매한다. 이용권은 모두 N장이고, 각 이용권에는 서로 다른 수업 하나를 한 번 들을 수 있는 권리가 들어 있다. 수업마다 준비물과 운영 시간이 달라 이용권의 가격도 다를 수 있다. 가격이 같은 이용권도 서로 다른 수업에 해당하므로 별개의 이용권으로 취급한다. 상담 창구에는 여러 학생이 찾아와 자신이 정한 예산으로 수업을 최대 몇 개까지 들을 수 있는지 묻는다. 학생은 원하는 이용권을 자유롭게 고를 수 있고, 이용권 하나를 고르면 그 가격을 전부 지불해야 한다. 한 이용권을 나누어 사거나 같은 이용권을 두 번 사는 일은 허용되지 않는다. 선택한 이용권 가격의 합이 예산과 정확히 같아도 구매할 수 있다. 할인이나 추가 수수료는 없다. 이 상담에서 수업의 시간표는 고려하지 않는다. 어떤 이용권들을 함께 골라도 수업에 모두 참여할 수 있다고 본다. 또한 학생은 특정 과목을 반드시 들어야 한다는 조건 없이, 오직 들을 수 있는 수업 수를 최대화하려 한다. 아무 이용권도 사지 않는 선택도 가능하며, 이때 지출 금액과 수업 수는 모두 0이다. 각 상담은 같은 이용권 목록을 바탕으로 독립적으로 진행한다. 앞선 학생에게 어떤 답을 알려 주었는지에 따라 이용권이 사라지거나 가격이 바뀌지 않는다. 상담은 실제 판매가 아니므로 다른 학생과 이용권을 나누어 가질 필요도 없다. 학생마다 주어진 예산에 대해 구매 가능한 이용권 수의 최댓값을 구한다. 최대 개수만 같다면 어떤 이용권을 선택했는지는 구별하지 않는다. 가장 싼 이용권조차 살 수 없는 예산이면 답은 0이고, 모든 이용권을 살 수 있는 예산이면 답은 N이다. 상담이 입력된 순서대로 각각의 답을 출력하는 프로그램을 작성한다.

입력

첫째 줄에 이용권 수 N과 상담 수 Q가 공백으로 구분되어 주어진다. N과 Q는 각각 1 이상 30,000 이하의 정수다.
둘째 줄에 이용권 가격 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 각 가격은 1 이상 1,000,000,000 이하의 정수다.
다음 Q개의 줄에 각 상담의 예산 B가 하나씩 주어진다. B는 0 이상 100,000,000,000,000 이하의 정수다.

출력

각 상담에 대해 예산을 넘지 않고 구매할 수 있는 이용권 수의 최댓값을 한 줄에 하나씩 출력한다. 출력 순서는 상담의 입력 순서와 같아야 한다.

5 6
8 3 6 3 11
0
3
6
12
20
31

0
1
2
3
4
5

4 4
5 5 5 5
4
5
19
20

0
1
3
4

출처: Devin.KR 자체 제작