(Memoization + Sorting ) Simple Algorithm 🔥🔥
Code\n\nclass Solution {\nprivate:\n    int n;\n    long long sum1, sum2;\n    vector<pair<int, int>> arr;\n\n    // finds max sum which can be made in t time w
# Code\n```\nclass Solution {\nprivate:\n    int n;\n    long long sum1, sum2;\n    vector<pair<int, int>> arr;\n\n    // finds max sum which can be made in t time with i as last index taken\n    // using simple knapsack dp - take, not take\n\n    long long dp[1001][1001];\n\n    long long f(vector<int>& nums1 ,int t , int i) {\n        // base case\n        if(t == 0 or i < 0)  return 0;\n        // memoization case\n        if(dp[t][i] != -1)  return dp[t][i];\n        // calling recursion\n        long long notTake = f(nums1, t, i - 1);\n        long long take = nums1[arr[i].second] + arr[i].first * 1ll * t\n            + f(nums1, t - 1, i - 1);\n        return dp[t][i] = max(take, notTake);\n    }\n\npublic:\n    int minimumTime(vector<int>& nums1 , vector<int>& nums2 , int x) {\n        // using exchange arguments\n        // Note:\n        // 1. we can clear all elements at most once\n        // 2. we need to clear elements in order of magnitude of nums2 elements\n\n        n = nums1.size();\n        sum1 = 0;\n        sum2 = 0;\n        arr = vector<pair<int, int>>();\n\n        for(int i = 0 ; i < n ; i++) {\n            arr.push_back({nums2[i] , i});\n            sum1 += nums1[i];\n            sum2 += nums2[i];\n        }\n\n        sort(arr.begin() , arr.end());\n        memset(dp, -1, sizeof(dp));\n\n        // using linear search\n        // note: dp matrix will be filled atmost once thus tle is prevented\n\n        for(int t = 0; t <= n; t++) {\n            long long sum = sum1 + t * sum2;\n            if(sum - f(nums1, t, n - 1) <= x)    return t;\n        }\n        return -1;\n    }\n};\n```
['Array', 'Dynamic Programming', 'Memoization', 'Sorting', 'C++']