def trace_down(all_bags, bag):
    """
    For the input bag "bag", trace down the path along all of its bags that it
    can hold and count them.
    """
    n = 0  # number of children seen at this level
    if len(bag.can_hold) == 0:
        return n
    for bag_type, n_can_hold in bag.can_hold.items():
        child_bag = all_bags[bag_type]
        for i in range(n_can_hold):
            n += 1  # count once for the child at this level
            n += trace_down(
                all_bags, child_bag
            )  # counts for all children at lower levels
    return n