[Java/C++/Python] DP Solution, O(n^2)
Intuition\nThe sa = sum(A), sb = sum(B).\nIf we do nothing,\nwe will have sb * i + sa in total at i seconds.\n\nAt the t seconds,\nwe will select t elements.\nT
# **Intuition**\nThe `sa = sum(A)`, `sb = sum(B)`.\nIf we do nothing,\nwe will have `sb * i + sa` in total at `i` seconds.\n\nAt the `t` seconds,\nwe will select `t` elements.\nTake a look at these selected elements,\n`A[i]` will be removed,\nand the sum for these elements is `b1 * (t - 1) + b2 * (t - 2) .... + bt * 0`.\nso `b1,b2,b3..,bt` are arranged in increasing order.\n<br>\n\n# **Explanation**\nFirstly we sort all pair of `(B[i], A[i])` by value of `B[i]`.\n\nThen we use `dp` to solve this prolem:\n`dp[j][i]` means the maximum value we can reduce at `i` seconds,\nwith `j + 1` step-smallest integers.\n\nThe `dp` equation is\n`dp[j][i] = max(dp[j][i], dp[j - 1][i - 1] + i * b + a)`\nFinally we return sconds `i`,\nif `sb * i + sa - dp[n - 1][i] <= x`,\notherwise return `-1`.\n\nSince we initial `dp[j] = dp[j - 1]`,\nactually we can save the first dimension,\nand improve the space to from `O(n^2)` to `O(n)`\n<br>\n\n# **Complexity**\nTime `O(n^2)`\nSpace `O(n)`\n<br>\n\n**Java**\n```java\n    public int minimumTime(List<Integer> A, List<Integer> B, int x) {\n        int n = A.size(), sa = 0, sb = 0, dp[] = new int[n + 1];\n        List<List<Integer>> BA = new ArrayList<>();\n        for (int i = 0; i < n; i++) {\n            int a = A.get(i), b = B.get(i);\n            BA.add(Arrays.asList(b, a));\n            sa += a;\n            sb += b;\n        }\n        Collections.sort(BA, (o1, o2) -> Integer.compare(o1.get(0), o2.get(0)));\n        for (int j = 0; j < n; ++j)\n            for (int i = j + 1; i > 0; --i)\n                dp[i] = Math.max(dp[i], dp[i - 1] + i * BA.get(j).get(0) + BA.get(j).get(1));\n        for (int i = 0; i <= n; ++i)\n            if (sb * i + sa - dp[i] <= x)\n                return i;\n        return -1;\n    }\n```\n\n**C++**\n```cpp\n    int minimumTime(vector<int>& A, vector<int>& B, int x) {\n        int n = A.size(), sa = accumulate(A.begin(), A.end(), 0), sb = accumulate(B.begin(), B.end(), 0);\n        vector<int> dp(n + 1);\n        vector<vector<int>> BA;\n        for (int i = 0; i < n; i++)\n            BA.push_back({B[i], A[i]});\n        sort(BA.begin(), BA.end());\n        for (int j = 0; j < n; ++j)\n            for (int i = j + 1; i > 0; --i)\n                dp[i] = max(dp[i], dp[i - 1] + i * BA[j][0] + BA[j][1]);\n        for (int i = 0; i <= n; ++i)\n            if (sb * i + sa - dp[i] <= x)\n                return i;\n        return -1;\n    }\n```\n\n**Python**\n```py\n    def minimumTime(self, A: List[int], B: List[int], x: int) -> int:\n        n = len(A)\n        dp = [0] * (n + 1)\n        for j, (b, a) in enumerate(sorted(zip(B, A)), 1):\n            for i in range(j, 0, -1):\n                dp[i] = max(dp[i], dp[i - 1] + i * b + a)\n        sa, sb = sum(A), sum(B)\n        for i in range(0, n + 1):\n            if sb * i + sa - dp[i] <= x:\n                return i\n        return -1\n```\n
['C', 'Python', 'Java']