LC 2809. 使数组和小于等于 x 的最少时间

https://leetcode.cn/problems/minimum-time-to-make-array-sum-at-most-x/description/

这题看了题解才知道怎么搞的。题解 https://leetcode.cn/problems/minimum-time-to-make-array-sum-at-most-x/solutions/2374920/jiao-ni-yi-bu-bu-si-kao-ben-ti-by-endles-2eho/

前面几步思路都差不多了，直到提示4这里。

这里是按照nums2的顺序，分别考虑保留t个子序列的代价，但是为什么这样可以是最优的呢？我其实还是有点疑惑的，大致可以这样想： 

class Solution:
    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:
        xs = list(zip(nums1, nums2))
        xs.sort(key=lambda x: x[1])

        s1 = sum(nums1)
        s2 = sum(nums2)

        n = len(nums1)
        f = [0] * (n + 1)
        f[0] = 0
        for a, b in xs:
            for j in reversed(range(1, n + 1)):
                f[j] = max(f[j], f[j - 1] + a + b * j)

        for t in range(n + 1):
            if (s1 + s2 * t - f[t]) <= x:
                return t
        return -1