Commented | Intuitive
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Solution:\n    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n        # Intuitive\n        # We don\'t neet 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.\n        # We need an order to process, otherwise try all orders and get O(N!)\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.\n        tup = [(nums2[i], nums1[i]) for i in range(len(nums1))]\n        tup.sort()\n        # Now that we have an order, we will need to find an optimal subset that will reduce the running sum to the required value. \n        # Trying all order == Optimal order + optimal subset.\n        # Any state involving runningSum will give TLE, since idx / time will be in the state.\n        # 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        N = len(nums1) + 1\n        dp = [[-1] * N for _ in range(N)]\n\n        def fn(idx: int, t: int) -> int:\n            if t == 0: return 0\n            if idx == -1: return float(\'-inf\')\n            \n            if dp[idx][t] != -1:\n                return dp[idx][t]\n\n            # ignore, ignoring means no time is used\n            ans = fn(idx - 1, t)\n            # take, taking one element corresponds to one second passing\n            ans = max(ans, tup[idx][1] + t * tup[idx][0] + fn(idx - 1, t - 1))\n            dp[idx][t] = ans\n            return ans \n\n        s = sum(nums1)\n        k = sum(nums2)\n        for t in range(0, len(nums1) + 1):\n            # 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.\n            if s + k * t - fn(len(nums1) - 1, t) <= x:\n                return t\n        return -1\n\n\n\n# Old, not so intuitive ----------------------------------------------------------\n        res = len(nums1) + 1\n        k = sum(nums2)\n        tup = [(nums2[i], nums1[i]) for i in range(len(nums1))]\n        tup.sort()\n        dp = [[0] * res for _ in range(res)]\n        \n        for idx in range(1, res):\n            for t in range(1, idx + 1):\n                dp[idx][t] = max(dp[idx - 1][t], dp[idx - 1][t - 1] + tup[idx - 1][1] + t * tup[idx - 1][0])\n        \n        s = sum(nums1)\n        for t in range(0, res):\n            if s + k * t - dp[-1][t] <= x:\n                res = min(res, t)\n\n        return res if res <= len(nums1) else -1\n\n# Previous TLE\n# class Solution:\n#     def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n#         res = len(nums1) + 1\n#         k = sum(nums2)\n#         tup = [(nums2[i], nums1[i]) for i in range(len(nums1))]\n#         tup.sort()\n#         print(tup)\n#         dp = {}\n\n#         def fn(idx: int, s: int, t: int):\n#             nonlocal res\n#             if s <= x:\n#                 res = min(res, t)\n#                 return\n#             if idx >= len(nums1):\n#                 return\n            \n#             key = (idx, s, t)\n#             if key in dp:\n#                 return\n            \n#             # take \n#             fn(idx + 1, s + k - tup[idx][1] - (t + 1) * tup[idx][0], t + 1)\n#             # leave\n#             fn(idx + 1, s, t)\n#             dp[key] = True\n        \n#         fn(0, sum(nums1), 0)\n#         return res if res <= len(nums1) else -1\n\n```
['Python3']