우체국의 예산별 발송 수

문제

한 우체국에 발송 대기 중인 소포 N개가 모여 있다. 각 소포에는 이미 확정된 발송 비용이 붙어 있으며, 담당자는 예산에 따라 최대 몇 개의 소포를 보낼 수 있는지 미리 계산하려고 한다. 소포의 크기와 목적지는 비용에 반영되어 있으므로, 계산할 때는 각 소포의 발송 비용만 고려하면 된다. 예산이 B원인 경우 담당자는 N개의 소포 중 원하는 소포를 골라 발송할 수 있다. 선택한 소포들의 발송 비용 합이 B원 이하여야 하며, 이 조건을 만족하면서 발송하는 소포의 개수를 최대화해야 한다. 비용이 같은 소포도 각각 별개의 소포이므로 모두 선택할 수 있다. 소포 하나를 나누어 일부만 발송하거나, 같은 소포를 두 번 발송하는 것은 허용하지 않는다. 소포를 하나도 선택하지 않는 것도 가능하며, 이때 필요한 비용과 발송 개수는 모두 0이다. 담당자는 서로 다른 예산을 가진 Q개의 검토안을 받았다. 각 검토안은 처음의 N개 소포 전체를 대상으로 독립적으로 계산한다. 앞선 검토안에서 선택한 소포가 다음 검토안에서 사라지거나, 발송 비용이 변경되는 일은 없다. 검토안의 예산은 주어진 순서대로 증가한다는 보장이 없고, 같은 예산이 여러 번 등장할 수도 있다. 어떤 예산에서 최대 발송 개수를 달성하는 소포 선택이 여러 가지라면, 그중 선택한 비용의 합이 가장 작은 값을 함께 보고해야 한다. 보고 대상은 최대 발송 개수와 그 개수를 달성하는 데 필요한 최소 비용뿐이다. 실제로 선택한 소포의 번호나 발송 순서는 출력하지 않는다. 최대 발송 개수가 0이면 최소 비용도 0으로 보고한다. 예산이 모든 소포의 비용 합 이상이면 N개를 모두 발송할 수 있다. 모든 발송 비용과 예산은 원 단위의 정수이다. 별도의 묶음 할인, 세금, 소포 간 우선순위는 없다. 각 검토안에 대해 보고해야 하는 두 값을 계산하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 Q가 주어진다. 1≤N≤20,000, 1≤Q≤10,000이다.
둘째 줄에 각 소포의 발송 비용 C_1, …, C_N이 주어진다. 모든 C_i는 정수이며 1≤C_i≤9,999이다.
다음 Q개 줄에 각 검토안의 예산 B가 하나씩 주어진다. B는 정수이며 0≤B≤200,000,000이다.

출력

각 검토안에 대해 최대 발송 개수와 그 개수를 달성하는 최소 비용을 공백으로 구분하여 한 줄에 출력한다. 검토안이 주어진 순서를 따른다.

5 4
8 3 6 3 12
0
9
12
100

0 0
2 6
3 12
5 32

4 3
5 5 5 5
4
10
19

0 0
2 10
3 15

출처: Devin.KR 자체 제작