<p>You are given two <strong>0-indexed</strong> integer arrays <code>nums1</code> and <code>nums2</code> of equal length. Every second, for all indices <code>0 &lt;= i &lt; nums1.length</code>, value of <code>nums1[i]</code> is incremented by <code>nums2[i]</code>. <strong>After</strong> this is done, you can do the following operation:</p>

<ul>
	<li>Choose an index <code>0 &lt;= i &lt; nums1.length</code> and make <code>nums1[i] = 0</code>.</li>
</ul>

<p>You are also given an integer <code>x</code>.</p>

<p>Return <em>the <strong>minimum</strong> time in which you can make the sum of all elements of </em><code>nums1</code><em> to be<strong> less than or equal</strong> to </em><code>x</code>, <em>or </em><code>-1</code><em> if this is not possible.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [1,2,3], nums2 = [1,2,3], x = 4
<strong>Output:</strong> 3
<strong>Explanation:</strong> 
For the 1st second, we apply the operation on i = 0. Therefore nums1 = [0,2+2,3+3] = [0,4,6]. 
For the 2nd second, we apply the operation on i = 1. Therefore nums1 = [0+1,0,6+3] = [1,0,9]. 
For the 3rd second, we apply the operation on i = 2. Therefore nums1 = [1+1,0+2,0] = [2,2,0]. 
Now sum of nums1 = 4. It can be shown that these operations are optimal, so we return 3.

</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [1,2,3], nums2 = [3,3,3], x = 4
<strong>Output:</strong> -1
<strong>Explanation:</strong> It can be shown that the sum of nums1 will always be greater than x, no matter which operations are performed.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code><font face="monospace">1 &lt;= nums1.length &lt;= 10<sup>3</sup></font></code></li>
	<li><code>1 &lt;= nums1[i] &lt;= 10<sup>3</sup></code></li>
	<li><code>0 &lt;= nums2[i] &lt;= 10<sup>3</sup></code></li>
	<li><code>nums1.length == nums2.length</code></li>
	<li><code>0 &lt;= x &lt;= 10<sup>6</sup></code></li>
</ul>

class Solution:
    def minimumTime(self, nums1: list[int], nums2: list[int], x: int) -> int:
        if sum(nums1) <= x:
            return 0
        n = len(nums1)
        nums = [(nums2[i], nums1[i], i) for i in range(n)]
        nums.sort()

        # cumsum[i][j]: cumulative sum of the jth index in nums after the (i+1)th second
        cumsum = []
        for i in range(n):
            cumsum.append([nums[j][1] + nums[j][0] * (i+1) for j in range(n)])

        # max_reduction[i][j]: maximum reduction by resetting only the indices among nums[:j+1] after the (i+1)th second
        max_reduction = [[0 for j in range(n)] for i in range(n)]

        # initialize max_reduction after the 1st second
        reduction = cumsum[0][0]
        for j in range(n):
            reduction = max(reduction, cumsum[0][j])
            max_reduction[0][j] = reduction
        
        total = sum(cumsum[0])
        if total - max_reduction[0][-1] <= x:
            return 1
        
        # initialize max_reduction assume we only reset the first index in nums
        for i in range(1, n):
            max_reduction[i][0] = cumsum[0][0]
        
        for i in range(1, n):
            total = sum(cumsum[i])
            for j in range(1, n):
                if i >= j:
                    max_reduction[i][j] = max_reduction[i][j-1] + cumsum[j][j]
                else:
                    max_reduction[i][j] = max(max_reduction[i][j-1], max_reduction[i-1][j-1] + cumsum[i][j])
            print(total, max_reduction[i][-1])
            if total - max_reduction[i][-1] <= x:
                return i+1
        return -1
85300