You have some apples and a basket that can carry up to `5000` units of weight.

Given an integer array `weight` where `weight[i]` is the weight of the `ith` apple, return _the maximum number of apples you can put in the basket_.

**Example 1:**

**Input:** weight = \[100,200,150,1000\]
**Output:** 4
**Explanation:** All 4 apples can be carried by the basket since their sum of weights is 1450.

**Example 2:**

**Input:** weight = \[900,950,800,1000,700,800\]
**Output:** 5
**Explanation:** The sum of weights of the 6 apples exceeds 5000 so we choose any 5 of them.

**Constraints:**

*   `1 <= weight.length <= 103`
*   `1 <= weight[i] <= 103`


def minHeightShelves(books, shelfWidth):
    n = len(books)
    dp = [1000000] * (n + 1)
    dp[0] = 0

    for i in range(1, n + 1):
        width = 0
        height = 0
        j = i
        while j >= 1:
            width += books[j - 1][0]
            height = max(height, books[j - 1][1])

            if width <= shelfWidth:
                dp[i] = min(dp[i], dp[j - 1] + height)
            j -= 1

    return dp[n]
