3462. Maximum Sum With at Most K Elements Medium

1/**
2 * [3462] Maximum Sum With at Most K Elements
3 *
4 * <p data-pm-slice="1 3 []">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:
5 * <ul data-spread="false">
6 * 	
7 * 	The number of elements taken from the i^th row of grid does not exceed limits[i].
8 * 	
9 * 
10 * <p data-pm-slice="1 1 []">Return the maximum sum.
11 *  
12 * <strong class="example">Example 1:
13 * <div class="example-block">
14 * Input: <span class="example-io">grid = [[1,2],[3,4]], limits = [1,2], k = 2</span>
15 * Output: <span class="example-io">7</span>
16 * Explanation:
17 * 
18 * 	From the second row, we can take at most 2 elements. The elements taken are 4 and 3.
19 * 	The maximum possible sum of at most 2 selected elements is 4 + 3 = 7.
20 * </div>
21 * <strong class="example">Example 2:
22 * <div class="example-block">
23 * Input: <span class="example-io">grid = [[5,3,7],[8,2,6]], limits = [2,2], k = 3</span>
24 * Output: <span class="example-io">21</span>
25 * Explanation:
26 * 
27 * 	From the first row, we can take at most 2 elements. The element taken is 7.
28 * 	From the second row, we can take at most 2 elements. The elements taken are 8 and 6.
29 * 	The maximum possible sum of at most 3 selected elements is 7 + 8 + 6 = 21.
30 * </div>
31 *  
32 * Constraints:
33 * 
34 * 	n == grid.length == limits.length
35 * 	m == grid[i].length
36 * 	1 <= n, m <= 500
37 * 	0 <= grid[i][j] <= 10^5
38 * 	0 <= limits[i] <= m
39 * 	0 <= k <= min(n * m, sum(limits))
40 * 
41 */
42pub struct Solution {}
43
44// problem: https://leetcode.com/problems/maximum-sum-with-at-most-k-elements/
45// discuss: https://leetcode.com/problems/maximum-sum-with-at-most-k-elements/discuss/?currentPage=1&orderBy=most_votes&query=
46
47// submission codes start here
48
49impl Solution {
50    pub fn max_sum(grid: Vec<Vec<i32>>, limits: Vec<i32>, k: i32) -> i64 {
51        
52    }
53}
54
55// submission codes end
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    #[test]
62    fn test_3462() {
63    }
64}
65