2d DP | O(n^2) Time, O(n) space.
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires us to find the minimum time needed to make the sum of the elements
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires us to find the minimum time needed to make the sum of the elements in **nums1** less than or equal to **x**. Every second, we can increment the elements of **nums1** by corresponding values in **nums2**, and we can also choose one element in **nums1** to set to 0.\n\n- Since setting the same position to 0 twice would be redundant, we can infer that the maximum time required would be equal to the length of **nums1**, denoted by **n**.\n- If we decide to reset **k** elements, we would choose them based on the order of their corresponding values in **nums2**. If we reset a larger **nums2[idx]** earlier, the increment would be larger.\n- We can use 2-dimensional Dynamic Programming (DP) to solve this problem. To save memory, we can use two vectors of length **n + 1**. **dp[i][j]** represents resetting **j** elements from the first **i** positions in the sorted **nums2**.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Initialization**: Find the sorted indices of **nums2** and initialize the dp vector with zeros.\n2. **Base Case**: Check if the initial sum of **nums1** is already less than or equal to **x**. If so, return 0.\n3. **Dynamic Programming**: Iterate through each time point, calculate the current sum, and use a new DP vector to calculate the maximum value considering the current time point. Check if the requirement is met and return the time point if so.\n4. **Final Check**: If no time point meets the requirement, return -1.\n\n# Complexity\n- Time complexity: $$O(n^2)$$. The nested loops iterate through **n** elements, resulting in quadratic time complexity.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$. We only use two vectors of length **n + 1**, resulting in linear space complexity.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n        n = len(nums1)\n        idxs = sorted(range(n), key=lambda x:nums2[x])\n        dp = [0] * (n + 1)\n        base = sum(nums1)\n        incr = sum(nums2)\n        # If already satisfies the requirement.\n        if base <= x:\n            return 0\n        \n        # Now, check each time point.\n        for time_point in range(1, n + 1):\n            curr_sum = base + incr * time_point\n            new_dp = [0] * (n + 1)\n            for i in range(time_point, n + 1): # We do not need to select y values from the first x elements if x < y.\n                new_dp[i] = max(new_dp[i - 1], dp[i - 1] + nums1[idxs[i - 1]] + time_point * nums2[idxs[i - 1]]) # The i th value has an index i - 1\n                if curr_sum - new_dp[i] <= x: # If requirement matches.\n                    return time_point\n            # Exchange\n            dp = new_dp\n        \n        # Not found\n        return -1\n```
['Python3']