공개 입찰 작업 스케줄링

계산량이 많은 작업을 일괄 처리하는 컴퓨팅 자원을 준비하고 있다. 시간 구간마다 정적 스케줄링을 쓰기로 했으므로, 후보 작업 묶음이 주어질 때마다 수입이 가장 커지는 조합을 골라야 한다.

작업은 공개 입찰로 받는다. 고객은 예약하려는 프로세서 시간을 초 단위로 적고, 그 대가로 낼 금액을 달러로 적는다. 작업이 일찍 끝나도 고객은 금액을 전부 낸다. 요청한 시간을 넘긴 작업은 중단되며, 이때도 고객은 금액을 전부 낸다. 스케줄을 짤 때는 모든 작업이 배정받은 시간을 끝까지 쓴다고 가정한다.

고객과의 관계를 생각해서, 남은 시간이 모자란 입찰은 스케줄에 넣지 않는다. 항공사처럼 초과 예약을 해 두고 누군가 배정 시간을 다 쓰지 않기를 바라는 방식은 쓰지 않는다.

정리하면, 요청 시간의 합이 주어진 시간을 넘지 않도록 입찰을 골라 지불 금액의 합을 최대로 만들어야 한다.

첫 줄에 파일에 들어 있는 문제 집합의 개수가 정수 하나로 주어진다.

문제 집합 하나는 n+2개의 줄로 이루어진다.

• 첫 줄에 스케줄링 후보 작업의 수 n이 주어진다. (n ≤ 500)
• 다음 n개의 줄에 입찰이 한 줄에 하나씩 주어진다. 각 줄은 초 단위 시간을 나타내는 정수, 공백 하나, 소수점 아래 두 자리까지 적은 달러 금액 순이다.
• 마지막 줄에 이 작업들로 채울 시간 t가 주어진다. (t ≤ 2000)

위에 적은 것 말고 다른 공백은 없다.

문제 집합마다 1번부터 번호를 붙여 한 줄씩 출력한다.

Problem <k>: <t> seconds scheduled for $abc.de

<k>는 문제 집합의 번호이고, <t>는 실제로 스케줄에 넣은 시간의 합이다. 입력으로 주어진 시간보다 작을 수 있다. 금액은 고른 입찰의 지불 금액 합이며, 앞에 통화 기호를 붙이고 소수점 아래 두 자리까지 적는다.

지불 금액의 합이 최대인 조합이 여럿이면 그중 시간의 합이 가장 작은 것을 출력한다.

빈 줄은 출력하지 않고, 마지막 줄도 줄바꿈 문자로 끝난다.