Minimum Sum of Values by Dividing Array
You are given two arrays nums and andValues of length n and m respectively.
The value of an array is equal to the last element of that array.
You have to divide nums into m disjoint contiguous subarrays such that for the i^th subarray [li, ri], the bitwise AND of the subarray elements is equal to andValues[i]. In other words, nums[li] & nums[li + 1] & ... & nums[ri] == andValues[i] for all 1 <= i <= m, where & represents the bitwise AND operator.
Return the minimum possible sum of the values of the m subarrays nums is divided into. If it is not possible to divide nums into m subarrays satisfying these conditions, return -1.
Example 1
Input
nums = [1,4,3,3,2], andValues = [0,3,3,2]Output
12The only possible division is
[1,4], [3], [3], and [2], giving value sum 4 + 3 + 3 + 2 = 12.Example 2
Input
nums = [2,3,5,7,7,7,5], andValues = [0,7,5]Output
17Among the valid divisions, the minimum possible sum of subarray values is
5 + 7 + 5 = 17.Constraints
- 1 <= n == nums.length <= 10^4
- 1 <= m == andValues.length <= min(n, 10)
- 1 <= nums[i] < 10^5
- 0 <= andValues[j] < 10^5