You are given an n $ imes$ m $2 ext{D}$ integer matrix grid, an integer array limits of length n, and an integer k.

Your task is to select at most k elements from grid such that the number of elements chosen from row i does not exceed limits[i].

Return the maximum possible sum of the chosen elements.

Constraints:

• n $==$ grid.length $==$ limits.length

• m $==$ grid[i].length

• $1 \leq$ n, m $\leq 500$

• $0 \leq$ grid[i][j] $\leq 10^5$

• $0 \leq$ limits[i] $\leq$ m

• $0 \leq$ k $\leq \min($n $ imes$ m, $ ext{sum}($`limits`$))$

Input: grid = [[0,5,2],[9,1,6]]-List[List[int]], limits = [2,1]-List[int], k = 2-int
Output: 14-int
Explanation: Select 5 from the first row and 9 from the second row, respecting the row limits and selecting at most 2 elements, for a maximum sum of 14.

Input: grid = [[14,3,11,8]]-List[List[int]], limits = [0]-List[int], k = 0-int
Output: 0-int
Explanation: No elements can be selected because both the row limit and k are 0, so the maximum sum is 0.

Input: grid = [[2,10,6],[13,1,8],[5,7,3]]-List[List[int]], limits = [1,2,1]-List[int], k = 4-int
Output: 38-int
Explanation: Select 10 from the first row, 13 and 8 from the second row, and 7 from the third row, respecting all row limits and obtaining a sum of 38.

Input: grid = [[100,4],[6,90],[8,7]]-List[List[int]], limits = [1,1,0]-List[int], k = 2-int
Output: 190-int
Explanation: Select 100 from the first row and 90 from the second row; no elements can be selected from the third row, giving a maximum sum of 190.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.