Two lines of dancers face each other. Dancer i of the left line has energy left[i] and dancer j of the right line has energy right[j]; energies may be negative. The choreographer picks some dancers from each line, the same number k >= 1 from both, and pairs them in line order: the first chosen left dancer with the first chosen right dancer, the second with the second, and so on. A pair scores the product of its two energies, and the routine scores the sum over its pairs.
Return the highest possible score. At least one pair must dance, so the answer can be negative.
Examples
Input: left = [2, 1, -2, 5], right = [3, 0, -6]
Output: 18
Explanation: pair 2 with 3 and -2 with -6: 6 + 12 = 18.
Input: left = [3, -2], right = [2, -6, 7]
Output: 21
Explanation: a single pair, 3 with 7.
Input: left = [-1, -1], right = [1, 1]
Output: -1
Constraints
1 <= len(left), len(right) <= 500-1000 <= left[i], right[j] <= 1000
Goals
- Adapt the two-sequence table to a sum of products
- Enforce that at least one pair is chosen
- Decide when a previous partial pairing is worth keeping