문제
식재료 N개 중에서 몇 개를 선택해서 이들의 영양분 (단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되도록 해야 한다.
아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택하여 이들의 영양분(단백질, 지방, 탄수화물, 비타민)의 각각 합이 최소 (100, 70, 90, 10)가 되도록 하는 경우를 생각해보자.
이 경우 모든 재료를 선택하면 쉽게 해결되지만 우리는 조건을 만족시키면서도 비용이 최소가 되는 합리적인 선택을 해야 한다.
예를 들어 식재료 {1, 3, 5}를 선택하면 영양분은 (100, 145, 130, 10)으로 조건을 만족하지만 가격은 270이 된다.
대신 {2, 3, 4}를 선택하면 영양분의 합은 (110, 130, 90, 10), 비용은 180이 되므로 앞서의 {1, 3, 5} 보다는 더 나은 선택이 된다.
여러분은 주어진 식재료 표에서 제시된 최저 영양소 기준을 만족하는 최소 비용의 식재료 집합을 찾아야 한다.
재료 | 단백질 | 지방 | 탄수화물 | 비타민 | 가격 |
|---|---|---|---|---|---|
1 | 30 | 55 | 10 | 8 | 100 |
2 | 60 | 10 | 10 | 2 | 70 |
3 | 10 | 80 | 50 | 0 | 50 |
4 | 40 | 30 | 30 | 8 | 60 |
5 | 60 | 10 | 70 | 2 | 120 |
6 | 20 | 70 | 50 | 4 | 40 |
입력
입력의 첫 줄에는 식재료의 개수를 뜻하는 정수 N(3≤N≤15)이 주어진다.
다음 줄에는 최소 영양성분을 나타내는 정수 mp, mf, ms, mv가 주어진다. (0≤mp,mf,ms,mv≤500, mp+mf+ms+mv>0)
이어지는 N개의 각 줄에는 i번째 식재료의 영양분과 가격이 5개의 정수로 pi, fi, si, vi, ci와 같이 주어진다.
(실제 입력에는 콤마 대신 빈칸을 사이에 두고 있다.) 이 값들은 0 이상 500 이하의 정수이다.
출력
여러분은 첫 번째 줄에 최소 비용을 출력하고, 두 번째 줄에 조건을 만족하는 최소 비용 식재료의 index를 오름차순으로 한 줄에 출력해야 한다.
같은 비용의 집합이 하나 이상이면 사전식으로 가장 빠른 것을 출력한다.
index는 1부터 센다.
만약 답이 없으면 첫 번째 줄에 -1을 출력하고, 두 번째 줄에 아무것도 출력하지 않는다.
예제1
6
100709010
3055108100
601010270
108050050
403030860
6010702120
20705044
134
246