정확한 거스름돈
면접 대비시간 제한1초메모리 제한128 MB
물건값과 100개 이하의 동전·지폐 값이 주어질 때, 합이 물건값 이상이면서 합을 최소로 하고 그다음 동전 개수를 최소로 하는 부분집합을 고른다.
문제
- 판매자: 14달러입니다.
- 구매자: 여기 20달러요.
- 판매자: 죄송하지만 거스름돈이 없네요.
- 구매자: 알겠습니다, 그럼 10달러와 5달러를 드릴게요. 거스름돈은 됐습니다.
외진 곳으로 여행할 때는 현금을 챙겨 가면 도움이 될 때가 많습니다. 신용카드나 직불카드를 받지 않는 사람에게서 물건을 사야 할 수도 있기 때문입니다. 또한 판매자가 거스름돈을 내주지 못할 경우를 대비해 여러 액면가의 화폐를 준비해 두는 것도 좋습니다. 그렇더라도 정확한 금액을 가지고 있지 않아, 제값보다 조금 더 내야 할 수도 있습니다. 이런 상황은 거스름돈을 돌려주지 않는 자판기처럼 도시에서도 생길 수 있습니다.
당신은 지불하는 금액을 최소화하고 싶지만, 최소한 물건 값 이상은 내야 합니다. 그리고 그 최소 금액을 내는 방법 중에서 사용하는 동전과 지폐의 개수도 가장 적게 하고 싶습니다.
입력
첫째 줄에 정수 하나, 곧 이어지는 테스트 케이스의 개수가 주어집니다.
각 테스트 케이스의 첫 줄에는 물건 값이 센트 단위 정수로 주어집니다. 가격은 10,000센트(즉 $100)를 넘지 않습니다. 다음 줄에는 가지고 있는 지폐와 동전의 개수 이 주어지며, 은 최대 100입니다. 이어지는 개의 줄에는 각각 지폐나 동전 하나의 가치가 센트 단위 정수로 주어집니다.
액면가는 임의의 센트 값일 수 있으며, 흔히 쓰는 동전과 지폐의 값으로 한정되지 않습니다. 다만 어떤 지폐나 동전도 10,000센트($100)를 넘지 않습니다. 가지고 있는 지폐와 동전의 총 가치는 항상 물건 값 이상입니다.
출력
각 테스트 케이스마다 한 줄에 두 정수를 출력합니다. 지불한 총 금액(센트 단위)과 사용한 동전 및 지폐의 총 개수입니다.