<div class="_1l1MA">It can be proven that in the optimal solution, for each index <code>i</code>, we only need to set <code>nums1[i]</code> to <code>0</code> at most once. (If we have to set it twice, we can simply remove the earlier set and all the operations “shift left” by <code>1</code>.)</div>

<div class="_1l1MA">It can also be proven that if we select several indexes <code>i₁, i₂, ..., i_k</code> and set <code>nums1[i₁], nums1[i₂], ..., nums1[i_k]</code> to <code>0</code>, it’s always optimal to set them in the order of <code>nums2[i₁] <= nums2[i₂] <= ... <= nums2[i_k]</code> (the larger the increase is, the later we should set it to <code>0</code>).</div>

<div class="_1l1MA">Let’s sort all the values by <code>nums2</code> (in non-decreasing order). Let <code>dp[i][j]</code> represent the maximum total value that can be reduced if we do <code>j</code> operations on the first <code>i</code> elements. Then we have <code>dp[i][0] = 0</code> (for all <code>i = 0, 1, ..., n</code>) and <code>dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + nums2[i - 1] * j + nums1[i - 1])</code> (for <code>1 <= i <= n</code> and <code>1 <= j <= i</code>).</div>

<div class="_1l1MA">The answer is the minimum value of <code>t</code>, such that <code>0 <= t <= n</code> and <code>sum(nums1) + sum(nums2) * t - dp[n][t] <= x</code>, or <code>-1</code> if it doesn’t exist.</div>