수족관의 세 장치

문제

수족관은 새 전시 수조에 설치할 환경 관리 장치를 고르고 있다. 설치 후보는 N개이며, 후보에는 입력되는 순서대로 1번부터 N번까지 번호가 붙는다. 각 후보 장치는 산소 공급량, 여과 처리량, 온도 유지량이라는 세 가지 성능과 구입 비용을 가진다. 세 성능은 각각 별도의 정수 단위로 측정하며, 서로 다른 성능을 합쳐서 다른 항목을 대신할 수는 없다. 수조 옆의 설치대에는 장치를 정확히 세 개 설치해야 한다. 같은 후보 장치를 두 번 선택할 수는 없으며, 장치 두 개만으로 필요한 성능을 채울 수 있더라도 세 번째 장치를 반드시 골라야 한다. 후보에는 각 장치가 한 개씩만 준비되어 있다. 성능과 비용이 모두 같은 후보가 여러 개 있더라도 번호가 다르면 서로 다른 장치다. 여러 장치를 설치했을 때 각 항목의 전체 성능은 선택한 장치들의 해당 성능을 더한 값이다. 장치 사이의 간섭이나 추가 보너스는 없다. 수조를 운영하려면 산소 공급량의 합이 X 이상이고, 여과 처리량의 합이 Y 이상이며, 온도 유지량의 합이 Z 이상이어야 한다. 세 조건을 모두 만족해야 하며, 필요한 양보다 성능이 높아지는 것은 허용한다. 관리자는 조건을 만족하는 세 장치 조합 중 구입 비용의 합이 가장 작은 조합을 선택하려 한다. 장치를 설치하는 순서는 비용이나 성능에 영향을 주지 않는다. 따라서 같은 세 장치를 순서만 바꾼 것은 하나의 조합으로 취급한다. 최소 비용을 달성하는 조합이 여러 개라면 각 조합의 번호를 오름차순으로 정렬하여 비교한다. 첫 번째 번호가 더 작은 조합을 우선하고, 첫 번째 번호가 같으면 두 번째 번호를 비교하며, 그것도 같으면 세 번째 번호가 더 작은 조합을 선택한다. 선택된 조합의 최소 비용과 세 번호를 구한다. 모든 후보를 살펴보아도 세 성능 조건을 만족하는 조합이 없다면 -1만 출력한다.

입력

첫째 줄에 정수 N, X, Y, Z가 공백으로 주어진다. 3 ≤ N ≤ 120이고, 0 ≤ X, Y, Z ≤ 3,000,000이다.
다음 N개 줄 중 i번째 줄에 i번 장치의 정수 성능 a_i, b_i, c_i와 구입 비용 p_i가 공백으로 주어진다. 각각 산소 공급량, 여과 처리량, 온도 유지량, 비용을 뜻한다. 0 ≤ a_i, b_i, c_i ≤ 1,000,000이고 1 ≤ p_i ≤ 1,000,000이다.

출력

가능한 조합이 있으면 첫째 줄에 최소 구입 비용의 합을 출력한다. 둘째 줄에 선택한 세 장치의 번호를 오름차순으로 공백으로 구분하여 출력한다. 최소 비용 조합이 여러 개이면 지문에 정한 번호 비교 규칙을 따른다. 가능한 조합이 없으면 첫째 줄에 -1만 출력한다.

5 10 10 10
6 1 2 4
1 6 2 4
3 3 6 5
5 5 5 9
4 4 4 9

13
1 2 3

4 3 3 3
1 1 1 2
1 1 1 2
1 1 1 2
1 1 1 2

6
1 2 3

3 4 4 4
1 1 1 1
1 1 1 2
1 1 1 3

-1

출처: Devin.KR 자체 제작