이번 문제는 백트레킹을 통해 해결하였다. 백트레킹을 통해 모든 경우를 구하고, 매 경우마다 기준치를 넘겼는지 확인한다. 만약 넘겼을 경우 정답 변수와 정답 리스트를 더 작은 것으로 갱신시켜주었다.

Code

n = int(input())
info = [[] for _ in range(n+1)]
dan, gi, tan, vi = map(int, input().split())
for i in range(1, n+1):
    d, g, t, v, c = map(int, input().split())
    info[i] = [d, g, t, v, c]
answer = 1e9
answer_path = []
def chk(cd, cg, ct, cv):
    if cd >= dan and cg >= gi and ct >= tan and cv >= vi:
        return True
    return False
def find_min(cur, cd, cg, ct, cv, cc, path):
    global answer, answer_path
    if chk(cd, cg, ct, cv):
        if answer > cc:
            answer = cc
            answer_path = path
    if cur == len(info):
        return
    if cc > answer:
        return
    find_min(cur+1, cd+info[cur][0], cg+info[cur][1], ct+info[cur][2], cv+info[cur][3], cc+info[cur][4], path+[cur])
    find_min(cur+1, cd, cg, ct, cv, cc, path)
find_min(1, 0, 0, 0, 0, 0, [])
if answer == 1e9:
    print(-1)
    quit()
print(answer)
print(*answer_path)