I want to optimize this code to make it run faster when given a variety of data. I would appreciate it if you could also include an explanation of the optimization method.

def parse_input():

    # Read the number of parts from the first line

    N = int(input().strip())

    

    parts = {'Body': [], 'Handle': [], 'Wheel': [], 'Engine': [], 'Booster': []}

    part_performance = {}

    

    for _ in range(N):

        category, name, performance = input().strip().split()

        performance = int(performance)

        parts[category].append((name, performance))

        part_performance[name] = performance

    

    # Read the number of synergies from the second line

    M = int(input().strip())

    

    synergies = {}

    for _ in range(M):

        part_a, part_b, synergy = input().strip().split()

        synergy = int(synergy)

        synergies[(part_a, part_b)] = synergy

        synergies[(part_b, part_a)] = synergy

    

    # Read the target performance S from the third line

    S = int(input().strip())

    

    return parts, part_performance, synergies, S



def find_best_combination(parts, part_performance, synergies, S):

    from itertools import product



    best_combination = None

    closest_performance = float('inf')

    

    for body, handle, wheel, engine, booster in product(parts['Body'], parts['Handle'], parts['Wheel'], parts['Engine'], parts['Booster']):

        combination = [body, handle, wheel, engine, booster]

        total_performance = sum(part[1] for part in combination)

        

        # Calculate synergy effects

        synergy_bonus = 0

        for i in range(5):

            for j in range(i + 1, 5):

                part1 = combination[i][0]

                part2 = combination[j][0]

                if (part1, part2) in synergies:

                    synergy_bonus += synergies[(part1, part2)]

        

        total_performance += synergy_bonus

        

        if abs(total_performance - S) < abs(closest_performance - S):

            closest_performance = total_performance

            best_combination = combination



    return best_combination



def main():

    parts, part_performance, synergies, S = parse_input()

    best_combination = find_best_combination(parts, part_performance, synergies, S)

    

    if best_combination:

        for part in best_combination:

            print(part[0])



if __name__ == "__main__":

    main()

This is an input example.

9

Body red 50

Body purple 50

Handle redsoft 30

Handle redhard 40

Handle purplesoft 30

Wheel purplehard 50

Engine redstrong 20

Engine purplecalm 10

Booster redcalm 10

5

red redsoft 20

red redhard 20

purplesoft purplehard 100

redstrong red 10

redstrong redcalm 50

169

Processing speed is not fast enough when input increases.