Maximum Sum With at Most K Elements
You are given a 2D integer matrix grid of size n x m, an integer array limits of length n, and an integer k.
The task is to find the maximum sum of at most k elements from the matrix grid such that:
- The number of elements taken from the
i^throw ofgriddoes not exceedlimits[i].
Return the maximum sum.
Example 1
1 2 3 4
Input
grid = [[1,2],[3,4]], limits = [1,2], k = 2Output
7From the second row, we can take 4 and 3, giving the maximum possible sum of at most 2 selected elements as 7.
Example 2
5 3 7 8 2 6
Input
grid = [[5,3,7],[8,2,6]], limits = [2,2], k = 3Output
21Taking 7 from the first row and 8 and 6 from the second row gives the maximum possible sum of at most 3 selected elements as 21.
Constraints
- n == grid.length == limits.length
- m == grid[i].length
- 1 <= n, m <= 500
- 0 <= grid[i][j] <= 10^5
- 0 <= limits[i] <= m
- 0 <= k <= min(n * m, sum(limits))