def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
    num_items: int = len(weights)
    row_len: int = -~capacity
    dp: list[int] = [0] * row_len

    for k in range(num_items * row_len):
        item_idx: int = k // row_len
        current_cap: int = capacity - (k % row_len)

        weight: int = weights[item_idx]
        value: int = values[item_idx]

        if weight <= current_cap:
            max_with_item: int = value + dp[current_cap - weight]

            if max_with_item > dp[current_cap]:
                dp[current_cap] = max_with_item

    return dp[capacity]