# input = """1:lampe rouge:1
# 2:petits rochers:0.5
# 1:lampe bleue:0.5
# 2:gros rochers:1.5"""
# target = 2

input = """1:X Wing:3567
1:Yoda (sans canne):41
7:rochers:13
3:blasters:0.5
1:D2R2:127
5:boîtes de de barres chocolatées:0.5
1:casque de pilote:2
1:lampe rouge:2
1:lampe bleue:1
1:canne de yoda:1
3:containers à bagages:7
2:branches de Gnarle:3
7:racines de Melacolie:1.5
1:sac à dos:12
1:serpent:12
4:oiseaux Jubba:3
2:lézards:0.5"""
target = 3892

sol = list()

def compute(items, target, config, sol):
    global masses
    if target == 0:
        if sorted(config) not in sol:
            print("1", end="")
            sol.append(sorted(config))
        return
    
    if target < 0:
        return

    if sum([masses[i] for i in items]) < target:
        return

    for i in range(len(items)):
        config_new = config.copy()
        config_new.append(items[i])
        target_new = target - masses[items[i]]
        items_new = items.copy()
        for _ in range(i+1):
            items_new.pop(0)
        items_new = [i for i in items_new if masses[i]<=target]
        compute(items_new, target_new, config_new, sol)


items = list()
masses = dict()
lines = input.splitlines()
for line in lines:
    qty, item, mass = line.split(":")
    qty = int(qty)
    mass = float(mass)
    masses[item] = mass
    for i in range(qty):
        items.append(item)

compute(items, target, list(), sol)

print()
for s in sol:
    print(s)
print(len(sol))

