급식 추가 주문 처리

문제

한 학교의 급식 주문 서비스는 점심 배식을 마친 뒤 남은 추가 식사를 판매한다. 백엔드 담당자는 접수된 주문을 순서대로 처리하고, 최종 재고와 결제 금액을 계산해야 한다. 처리 시작 시 추가 식사는 S개 남아 있으며, 식사 한 개의 가격은 P원이다. 처리 도중 식사가 새로 들어오거나 가격이 바뀌는 일은 없다. 접수된 주문은 모두 N건이며, 각 주문에는 구매하려는 식사 수량이 양의 정수로 기록되어 있다. 주문은 입력에 주어진 순서대로 하나씩 처리한다. 어떤 주문의 수량이 그 주문을 처리하기 직전의 재고 이하라면 주문 전체를 승인한다. 승인한 주문의 수량만큼 재고를 줄이고, 주문 수량에 P를 곱한 금액을 누적 결제 금액에 더한다. 재고가 주문 수량과 정확히 같을 때도 주문을 승인하며, 이 경우 재고는 0이 된다. 주문 수량이 현재 재고보다 많으면 해당 주문 전체를 거절한다. 일부 수량만 판매하는 부분 승인은 하지 않는다. 거절된 주문은 재고와 누적 결제 금액을 바꾸지 않는다. 거절된 주문을 뒤로 미루거나 나중에 다시 처리하지도 않는다. 따라서 앞선 주문이 거절되었더라도 뒤에 들어온 더 작은 주문은 남은 재고에 따라 승인될 수 있다. 모든 주문을 처리한 뒤 남은 식사 수량과 실제 승인된 주문들의 누적 결제 금액을 구하는 프로그램을 작성한다. 초기 누적 결제 금액은 0원이며, 수수료나 할인은 없다. 초기 재고가 0이거나 어떤 주문도 승인되지 않았다면 결제 금액은 0원이다. 주문이 한 건도 없는 경우에는 초기 재고가 그대로 남는다. 처리 순서가 정해져 있으므로 승인할 주문을 따로 선택하거나 결제 금액을 최대화할 필요는 없다.

입력

첫째 줄에 정수 S, P, N이 공백으로 구분되어 주어진다. 0 ≤ S ≤ 1,000, 1 ≤ P ≤ 1,000, 0 ≤ N ≤ 1,000이다.
다음 N개의 줄에 주문 수량을 나타내는 정수 Q가 하나씩 주어진다. 각 주문에 대해 1 ≤ Q ≤ 1,000이다. N이 0이면 주문 수량을 나타내는 줄은 주어지지 않는다.

출력

모든 주문을 처리한 뒤 남은 식사 수량과 누적 결제 금액을 이 순서대로 공백으로 구분하여 한 줄에 출력한다. 금액은 원 단위 정수로 출력한다.

7 120 4
5
4
2
1

0 840

0 500 2
1
3

0 0

9 250 0

9 0

출처: Devin.KR 자체 제작