체험 상품 장바구니

문제

한 온라인 쇼핑몰은 새로 가입한 회원에게 체험 상품을 고를 수 있는 전용 예산을 제공한다. 체험 상품 목록에는 N개의 상품 항목이 있으며, 각 항목에는 정수 가격이 붙어 있다. 회원은 목록의 각 항목을 최대 한 번 구매할 수 있다. 서로 다른 항목의 가격이 같을 수 있으며, 가격이 같더라도 각각 별개의 상품으로 센다. 상품을 구매하는 순서는 자유롭고, 목록에 나타난 순서를 따를 필요는 없다. 쇼핑몰의 장바구니 추천 기능은 주어진 예산 B로 구매할 수 있는 상품의 개수를 최대화하려고 한다. 상품 가격의 합이 B 이하이면 구매 가능한 장바구니다. 예산과 가격 합이 정확히 같아도 구매할 수 있다. 상품 하나를 나누어 구매하거나 같은 항목을 여러 번 구매할 수는 없다. 이번 행사에서는 배송비, 세금, 할인, 적립금이 모두 없으므로 결제 금액은 고른 상품들의 가격을 단순히 더한 값이다. 가장 많은 상품을 담는 방법이 여러 가지라면, 그중 결제 금액이 가장 작은 방법을 선택한다. 따라서 출력할 남은 예산은 최대 개수의 상품을 구매하는 방법 중 가장 크게 남길 수 있는 금액이 된다. 상품 개수와 결제 금액까지 같은 방법이 여러 개라면 어느 방법을 선택해도 결과가 같으므로 상품 번호에 따른 추가 우선순위는 없다. 실제로 선택한 상품의 목록도 출력하지 않는다. 예산이 부족하여 상품을 하나도 구매할 수 없다면 구매 개수는 0이고 남은 예산은 B 그대로다. 모든 상품을 구매하고도 예산이 남는 경우에는 남은 금액을 그대로 기록한다. 상품 가격 목록과 예산이 주어질 때, 추천 기능이 선택할 구매 개수와 남은 예산을 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 B가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100,000, 0 ≤ B ≤ 1,000,000,000)
둘째 줄에 각 상품 항목의 가격을 나타내는 정수 P₁, P₂, …, Pₙ이 공백으로 구분되어 주어진다. (1 ≤ Pᵢ ≤ 99)
가격이 같은 상품 항목도 각각 한 번씩 구매할 수 있다.

출력

최대로 구매할 수 있는 상품 개수와, 그 개수를 구매하면서 결제 금액을 최소화했을 때의 남은 예산을 공백으로 구분하여 한 줄에 출력한다.

6 17
8 3 5 3 9 4

4 2

3 1
2 2 7

0 1

4 20
4 4 4 4

4 4

출처: Devin.KR 자체 제작