main.py

import sys


def better(left, right):
    if right is None:
        return True
    if left[0] != right[0]:
        return left[0] > right[0]
    return left[1] < right[1]


def solve(data: str) -> str:
    tokens = data.split()
    if not tokens:
        return ""
    it = iter(tokens)
    n = int(next(it))
    limit_h = int(next(it))
    limit_m = int(next(it))
    names = []
    items = []
    for _ in range(n):
        name = next(it)
        hours = int(next(it))
        materials = int(next(it))
        profit = int(next(it))
        names.append(name)
        items.append((hours, materials, profit))
    zero = tuple([0] * n)
    dp = [[None for _ in range(limit_m + 1)] for _ in range(limit_h + 1)]
    dp[0][0] = (0, zero)
    for h in range(limit_h + 1):
        for m in range(limit_m + 1):
            state = dp[h][m]
            if state is None:
                continue
            profit, counts = state
            for index, (hours, materials, value) in enumerate(items):
                nh = h + hours
                nm = m + materials
                if nh > limit_h or nm > limit_m:
                    continue
                next_counts = list(counts)
                next_counts[index] += 1
                candidate = (profit + value, tuple(next_counts))
                if better(candidate, dp[nh][nm]):
                    dp[nh][nm] = candidate
    best = (0, zero)
    for h in range(limit_h + 1):
        for m in range(limit_m + 1):
            state = dp[h][m]
            if state is not None and better(state, best):
                best = state
    plan = ",".join(f"{name}:{count}" for name, count in zip(names, best[1]))
    return f"best_profit={best[0]}\nplan={plan}"


if __name__ == "__main__":
    sys.stdout.write(solve(sys.stdin.read()).strip())
    sys.stdout.write("\n")