DP + Greedy | Intuitive
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```python3 []
class Solution:
    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:
        # Intuitive
        # We don't need to make one element zero more than once, why? becuase if you're doing so, just skip the first instance where you made it zero, since it was useless.
        # We need an order to process, otherwise try all orders and get O(N!)
        # With exchange arguments we can tell we should process in nums2 asc order for most reduction or quickly reducing the sum to a lower value.
        tup = [(nums2[i], nums1[i]) for i in range(len(nums1))]
        tup.sort()
        # Now that we have an order, we will need to find an optimal subset that will reduce the running sum to the required value. 
        # Trying all order == Optimal order + optimal subset.
        # Any state involving runningSum will give TLE, since idx / time will be in the state.
        # We can try to find the max reduction we can get with t seconds, these t seconds will correspond to the subset we're using. 
        N = len(nums1) + 1
        dp = [[-1] * N for _ in range(N)]

        def fn(idx: int, t: int) -> int:
            if t == 0: return 0
            if idx == -1: return float('-inf')
            
            if dp[idx][t] != -1:
                return dp[idx][t]

            # ignore, ignoring means no time is used
            ans = fn(idx - 1, t)
            # take, taking one element corresponds to one second passing
            ans = max(ans, tup[idx][1] + t * tup[idx][0] + fn(idx - 1, t - 1))
            dp[idx][t] = ans
            return ans 

        s = sum(nums1)
        k = sum(nums2)
        
        for t in range(0, len(nums1) + 1):
            # Why process tup in reverse order so we can calculate the dp with just two states, we will use the passed t in internal calculation.
            # time is same as using t elements.
            if s + k * t - fn(len(nums1) - 1, t) <= x:
                return t
        return -1


```
['Python3']