모든 언어에 대해 시간 제한 2초, 메모리 제한 512MB입니다. 

식재료 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개의 정수로 p_i, f_i, s_i, v_i, c_i와 같이 주어진다. (실제 입력에는 콤마 대신 빈칸을 사이에 두고 있다.) 이 값들은 0 이상 500 이하의 정수이다.

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

만약 답이 없으면 첫 번째 줄에 -1을 출력하고, 두 번째 줄에 아무것도 출력하지 않는다.

2020KOI1차