다이어트

면접 대비

시간 제한2초메모리 제한512 MB

요약

최대 15개의 재료 중 일부를 골라 단백질, 지방, 탄수화물, 비타민 합이 각 기준 이상이 되게 하면서 가격을 최소로 하고, 같은 가격이면 번호 집합이 사전순으로 가장 작은 것을 찾는다.

난이도: 보통10점 중 5점
유형: 완전 탐색, 백트래킹, 재귀, 구현
정답자: 아직 제출이 없습니다

문제

식재료 $N$ 개 중에서 몇 개를 골라 단백질, 탄수화물, 지방, 비타민의 합이 각각 일정 기준 이상이 되도록 하려고 한다. 아래 표에 있는 6가지 식재료 중에서 몇 개를 골라 각 영양소의 합이 최소 100, 70, 90, 10이 되도록 하는 경우를 생각해 보자. 모든 재료를 고르면 조건을 쉽게 만족하지만, 우리는 조건을 만족하면서 비용이 최소가 되는 선택을 하려고 한다.

재료	단백질	지방	탄수화물	비타민	가격
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

예를 들어 식재료 1, 3, 5를 고르면 영양소 합은 100, 145, 130, 10으로 조건을 만족하지만 가격은 270이 된다. 대신 2, 3, 4를 고르면 영양소 합은 110, 130, 90, 10이고 비용은 180이므로, 앞의 선택보다 낫다.

식재료 표가 입력으로 주어졌을 때, 최저 영양소 기준을 만족하는 최소 비용의 식재료 집합을 찾아야 한다.

입력

첫 줄에 식재료의 개수 $N$ 이 주어진다.

다음 줄에는 단백질, 지방, 탄수화물, 비타민의 최소 영양성분을 나타내는 정수 $mp$ , $mf$ , $ms$ , $mv$ 가 주어진다.

이어지는 $N$ 개의 각 줄에는 $i$ 번째 식재료의 단백질, 지방, 탄수화물, 비타민과 가격이 5개의 정수 $p_i$ , $f_i$ , $s_i$ , $v_i$ , $c_i$ 와 같이 주어진다. 식재료의 번호는 1부터 시작한다.

출력

첫 번째 줄에 최소 비용을 출력하고, 두 번째 줄에 조건을 만족하는 최소 비용 식재료의 번호를 공백으로 구분해 오름차순으로 한 줄에 출력한다. 같은 비용의 집합이 하나 이상이면 사전 순으로 가장 빠른 것을 출력한다.

조건을 만족하는 답이 없다면 -1을 출력하고, 둘째 줄에 아무것도 출력하지 않는다.

제한

$3 \le N \le 15$
$0 \le mp, mf, ms, mv \le 500$
$mp + mf + ms + mv > 0$
$0 \le p_i, f_i, s_i, v_i, c_i \le 500$

예제1

예제 1

입력

6
100 70 90 10
30 55 10 8 100
60 10 10 2 70
10 80 50 0 50
40 30 30 8 60
60 10 70 2 120
20 70 50 4 4

예상 출력

134
2 4 6

재료	단백질	지방	탄수화물	비타민	가격
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

재료	단백질	지방	탄수화물	비타민	가격
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

재료	단백질	지방	탄수화물	비타민	가격
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