def days_needed(weights: list[int], s: int) -> int:
    days = 1
    capacity = s
    for weight in weights:
        if capacity - weight >= 0:
            capacity -= weight
        else:
            capacity = s - weight
            days += 1
    return days


class Solution:
    def shipWithinDays(self, weights: list[int], days: int) -> int:
        lo, hi = max(weights), sum(weights)
        while lo < hi:
            s = (lo + hi) // 2
            if days_needed(weights, s) > days:
                lo = s + 1
            else:
                hi = s

        return lo