def capacity_to_ship_packages(weights, days):
    smallest_possible_capacity = 1
    while True:
        # Keep testing increasingly larger capacities until we find one that works
        if can_ship_all_packages(weights, days, smallest_possible_capacity):
            return smallest_possible_capacity
        smallest_possible_capacity += 1

def can_ship_all_packages(weights, days, current_capacity):
    number_of_days_needed = 1
    current_weight_on_truck = 0

    for weight in weights:
        # If adding the next package exceeds the current capacity, move to the next day
        if current_weight_on_truck + weight > current_capacity:

            number_of_days_needed += 1
            current_weight_on_truck = 0

        current_weight_on_truck += weight

        # If we exceeded the total number of days allowed, this capacity is too small
        if number_of_days_needed > days:

            return False

    return True

def capacity_to_ship_packages_within_d_days(weights, days):
    minimum_capacity = max(weights)
    maximum_capacity = sum(weights)

    while minimum_capacity < maximum_capacity:
        mid_capacity = (minimum_capacity + maximum_capacity) // 2
        days_needed = 1
        current_load = 0

        for weight in weights:
            if current_load + weight > mid_capacity:
                # Need a new day, so increment the day count.
                days_needed += 1
                current_load = 0

            current_load += weight

        # If we need more days, the capacity is too small.
        if days_needed > days:
            minimum_capacity = mid_capacity + 1

        else:
            # This capacity works, try to find a smaller one.
            maximum_capacity = mid_capacity

    return minimum_capacity