Tag: dfs

# 계산

def calculate(num1, num2, operator):

    if operator == '+':
        num1 += num2
    elif operator == '-':
        num1 -= num2
    elif operator == '*':
        num1 *= num2
    elif operator == '/':
        num1 = int(num1 / num2)
    return num1

# 수식 완성
def search_expression(i, result):
    if i == n:
        global max_num, min_num
        max_num = max(max_num, result)
        min_num = min(min_num, result)
        return

    for operator in operators:
        if operator_dict[operator] > 0:
            operator_dict[operator] -= 1
            search_expression(i + 1, calculate(result, nums[i+1], operator))
            operator_dict[operator] += 1



test_case = int(input())

for t in range(test_case):
    n = int(input()) - 1
    operators = ['+', '-', '*', '/']
    operator_dict = {operator: cnt for operator, cnt in zip(operators, map(int, input().split()))}

    nums = list(map(int, input().split()))

    max_num = float('-inf')
    min_num = float('inf')
    result_dict = {}
    visited = []

    search_expression(0, nums[0])

    print(f"#{t + 1} {max_num - min_num}")

test_case = int(input())


# 제한 칼로리 내에서 최대의 맛
def search_best(hamburgers, sum_cal=0, sum_score=0):
    global max_score
    max_score = max(max_score, sum_score)

    for i, (score, cal) in enumerate(hamburgers):
        if sum_cal + cal > l:
            continue
        search_best(hamburgers[i + 1:], sum_cal + cal, sum_score + score)


for t in range(test_case):
    n, l = map(int, input().split())

    hamburgers = [list(map(int, input().split())) for _ in range(n)]

    max_score = 0

    search_best(hamburgers)

    print(f"#{t + 1} {max_score}")