Taking same number a second time is same as taking it only one time
Intuition\nKey Observations:\n1. If you take nums[i] both at time 2 and at time 5, the result is same as taking nums[i] only at time 5. And taking only at time 
# Intuition\nKey Observations:\n1. If you take nums[i] both at time 2 and at time 5, the result is same as taking nums[i] **only** at time 5. And taking **only** at time 5 is better because you save one extra round. \nBecause of this, it make no sense to take any index a second time. Each index can only be taken once. We only need to consider n number of time.\n2. If time is decided, mimimum remaining sum can be calculated using maximum sum taken away.\n3. If both time and indexes to take are decided, we can easily find out the max sum that can be taken away. Just sum all nums1 in given indexes, and sort nums2 in the given indexes from big to small.\n3. Now we need to list all combinations of indexes at given time, and find out which combination offers the biggest sum that can be taken away.\nCombination problem can typically be optimized by DP, by scanning each index and decide to "take-or-not-take" it.\n\n# Complexity\nTime: O(n^2)\nSpace: O(n)\nThe top-down recursive memorization appraoch is straightforward, but will exceed **memory** limit for its O(n^2) memroy. To pass we have to translate the recursive way to iterative way so as to save one extra demension of memory.\nThis is probably the first question in leetcode that set stricker memory limit than time limit. \n\n\n# Code\nRecursive approach (memory limit exceeded):\n``` python\n    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n        n = len(nums1)\n        A = sorted(zip(nums2,nums1),reverse=True)\n        @cache\n        def dp(i,time):\n            if i>=n or not time: \n                return 0\n            take = A[i][0]*time+A[i][1] + dp(i+1,time-1)\n            noTake = dp(i+1,time)\n            return max(take,noTake)\n        sm1,sm2 = sum(nums1),sum(nums2)\n        for time in range(n+1):\n            if (sm2*time + sm1 - dp(0,time)) <= x:\n                return time\n        return -1\n```\n\nIterative approach translated from recursive (Pass):\n``` python\nclass Solution:\n    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n        n = len(nums1)\n        sm1,sm2 = sum(nums1),sum(nums2)\n        if sm1<=x:\n            return 0\n        A = sorted(zip(nums2,nums1))\n        dp = [0]*(n+1)\n        for time in range(1,n+1):\n            dp2 = [0]*(n+1)\n            for i in range(n):\n                take = A[i][0]*time+A[i][1]+dp[i-1]\n                noTake = dp2[i-1]\n                dp2[i] = max(take,noTake)\n            dp = dp2\n            if (sm2*time+sm1-dp[n-1]) <= x:\n                return time\n        return -1\n```
['Python3']