import sys
sys.stdin = open("input.txt", "r")
from itertools import combinations as cb
T = int(input())
for test_case in range(1, T + 1):
N, totalCal = map(int, input().split())
answer, tempList = 0, []
for i in range(N):
score, cal = map(int, input().split())
tempList.append([score, cal])
# 모든 가능한 조합 탐색 (2^21 -> 완전탐색 가능)
for repeat in range(1, N+1):
combCal = [sum(t[1] for t in x) for x in cb(tempList, repeat)]
combScore = [sum(t[0] for t in x) for x in cb(tempList, repeat)]
for idx, item in enumerate(combCal):
if item <= totalCal:
answer = max(answer, combScore[idx])
print("#" + str(test_case) + " " + str(answer))
우선 모든 가능한 경우를 조합으로
나타내도 타임 아웃이 걸리지 않는다는 것을 파악하면 매우 쉬운 문제이다. (D3)
다만 score, cal를 하나의 자료구조로 넣고 그 안에서 조합을 돌려 특정 부분에서만 합(sum)을 구하는 로직을 잘 기억해두자.
combCal = [sum(t[1] for t in x) for x in cb(tempList, repeat)]
이런 식으로 조합을 돌린 구조에 item에서의 t(한번 더 참조) 가 들어가면 해결할 수 있다.