시간제한 : 10초
설명
알프레드는 앞으로 어떤 요리를 할 지 계획을 세우려고 한다. 그는 다양한 요리를 할 수 있는데, 각 요리를 하는 데 드는 비용과 그 요리를 통해 얻는 만족도는 정해져 있다. 그가 만약 어떤 요리를 첫 번째로 한다면, 그는 그 요리가 주는 만족도 만큼의 만족을 얻을 수 있다. 하지만 그가 같은 요리를 다음날에 또 한다면, 그는 그 요리가 주는 만족도 * 0.5 만큼의 만족밖에 얻지 못하며, 3번째나 그 이후는 같은 요리를 하면 전혀 만족을 얻지 못한다.
예를 들어, 만족도가 v인 요리를 3일간 하면, 그는 1.5*v만큼의 만족을 얻는다.
입력 설명
입력은 여러 개의 테스트 케이스로 이루어질 수 있다. 각 테스트 케이스는 3개의 정수(요리 계획을 세울 날의 수 k(1<=k<=21), 알프레드가 할 수 있는 요리의 수 n(1<=n<=50), 알프레드가 가진 돈 m(1<=m<=100))를 포함하는 한 줄로 시작한다. 이후에 오는 n개의 줄에는 알프레드가 할 수 있는 요리에 대한 정보가 나열된다. 각 줄에는 요리를 하는 데 드는 비용 c(1<=c<=50), 요리를 통해 얻을 수 있는 만족 v(1<=v<=10,000)이 주어진다. k=n=m=0일 때 입력을 종료한다.
출력 설명
각 테스트 케이스에 대해 얻을 수 있는 최대의 만족을 소수점 한 자리까지 출력한다. 그 다음에는 k개의 정수를 출력한다. 이는 각 날에 어떤 요리를 할 것인지에 대한 정보이다. 요리는 1부터 n까지 번호를 붙인다. 같은 만족을 얻을 수 있는 계획이 여러 개 존재할 경우, 그 중 가장 가격이 적은 것을 출력하며, 가격이 모두 같을 경우 아무 것이나 출력해도 된다. 어떠한 방법으로도 주어진 돈 이내에서 계획을 짤 수 없는 경우, 0을 출력한다. 각 정수 사이에는 공백이나 개행 문자를 출력한다.
입력 예제
2 1 5
3 5
3 5 20
2 5
18 6
1 1
3 3
2 3
0 0 0
출력 예제
0.0
13.0
1 5 1
퍼가고자 하시는 분은 링크를 달아 주시기 바랍니다.
댓글을 달아 주세요