다이어트

식재료 $N$개 중 몇 개를 선택하려고 한다. 선태한 식재료의 단백질, 지방, 탄수화물, 비타민의 합이 각각 주어진 최소량 이상이어야 한다.

각 식재료에는 단백질, 지방, 탄수화물, 비타민의 양과 가격이 주어진다. 조건을 만족하는 선택 중 가격의 합이 가장 작은 것을 찾아보자.

예를 들어 다음 $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

최소 영양분이 단백질 $100$, 지방 $70$, 탄수화물 $90$, 비타민 $10$이라면,

• 식재료 ${1, 3, 5}$의 영양분 합은 $(100, 145, 130, 10)$, 가격은 $270$이다.
• 식재료 ${2, 3, 4}$의 영양분 합은 $(110, 120, 90, 10)$, 가격은 $180$이다.

따라서 ${2, 3, 4}$가 더 좋은 선택이다.

조건을 만족하는 식재료들의 최소 비용과 그때 선택한 식재료들을 구하여라.

첫째 줄에 식재료의 개수 $N$이 주어진다. $(3 \le N \le 15)$

둘째 줄에 필요한 단백질, 지방, 탄수화물, 비타민의 최소 영양분 $mp$, $mf$, $ms$, $mv$가 차례로 주어진다. $(0 \le mp, mf, ms, mv \le 500$, $mp + mf + ms + mv > 0)$

다음 $N$개의 줄에는 $i$번째 식재료의 단백질, 지방, 탄수화물, 비타민, 그리고 가격을 나타내는 5개의 정수 $p_{i}$, $f_{i}$, $s_{i}$, $v_{i}$, $c_{i}$가 공백으로 구분되어 주어진다. 모든 값은 $0$ 이상 $500$ 이하의 정수이다.

조건을 만족하도록 식재료를 선택했을 때의 최소 비용을 첫째 줄에 출력한다.

둘째 줄에는 선택한 식재료의 번호를 오름차순으로 출력한다. 번호는 $1$부터 시작한다.

최소 비용이 같은 선택이 여러 개라면, 번호들을 앞에서부터 비교했을 때 가장 먼저 작은 수가 나오는 선택을 출력한다. 조건을 만족하는 선택이 없다면 첫째 줄에 -1만 출력한다.