You are given an m x n integer matrix mat and an integer target.

Choose one integer from each row in the matrix such that the absolute difference between target and the sum of the chosen elements is minimized.

Return the minimum absolute difference.

The absolute difference between two numbers a and b is the absolute value of a - b.

&nbsp;
Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], target = 13
Output: 0
Explanation: One possible choice is to:
- Choose 1 from the first row.
- Choose 5 from the second row.
- Choose 7 from the third row.
The sum of the chosen elements is 13, which equals the target, so the absolute difference is 0.


Example 2:

Input: mat = [[1],[2],[3]], target = 100
Output: 94
Explanation: The best possible choice is to:
- Choose 1 from the first row.
- Choose 2 from the second row.
- Choose 3 from the third row.
The sum of the chosen elements is 6, and the absolute difference is 94.


Example 3:

Input: mat = [[1,2,9,8,7]], target = 6
Output: 1
Explanation: The best choice is to choose 7 from the first row.
The absolute difference is 1.


&nbsp;
Constraints:


	m == mat.length
	n == mat[i].length
	1 &lt;= m, n &lt;= 70
	1 &lt;= mat[i][j] &lt;= 70
	1 &lt;= target &lt;= 800


class Solution:
    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
        min_possible = sum(min(row) for row in mat)
        if min_possible >= target: return min_possible - target
        curs = {0}
        for row in mat:
            curs = {x + y for x in row for y in curs if x + y <= 2*target}
        return min(abs(target - x) for x in curs)
class Solution {
    public int minimizeTheDifference(int[][] mat, int target) {
        Integer[][] dp = new Integer[mat.length][5001];
        return minDiff(mat, 0, target,0, dp);
    }

    public int minDiff(int[][] mat,int index,int target, int val, Integer[][] dp){
        if(index == mat.length){
            return Math.abs(val - target);
        }
        if(dp[index][val] != null){
            return dp[index][val];
        }

        int res = Integer.MAX_VALUE;
        for(int i = 0; i < mat[0].length; i++){
            res = Math.min(res, minDiff(mat, index + 1, target, val + mat[index][i], dp));
        }

        return dp[index][val] = res;
    }
}
class Solution 
{
public:
    int dp[8000][71];
    int n,m;
    int find(vector<vector<int>>&mat,int r,int sum,int &target)
    {
        if(r>=n)
        {
            return abs(sum-target);
        }
        if(dp[sum][r]!=-1)
        {
            return dp[sum][r];
        }
        int ans=INT_MAX;
        for(int i=0;i<m;i++)
        {
            ans=min(ans,find(mat,r+1,sum+mat[r][i],target));
            if(ans==0)
            {
                break;
            }
        }
        return dp[sum][r]=ans;
    }
    int minimizeTheDifference(vector<vector<int>>& mat, int target) 
    {
        memset(dp,-1,sizeof(dp));
        n=mat.size();
        m=mat[0].size();
        return find(mat,0,0,target);
    }
};
var minimizeTheDifference = function(mat, target) {
    const MAX = Number.MAX_SAFE_INTEGER;
    
    const m = mat.length;
    const n = mat[0].length;
    
    const memo = [];
    
    for (let i = 0; i < m; ++i) {
        memo[i] = new Array(4901).fill(MAX);
    }
    
    return topDown(0, 0);
    
    function topDown(row, sum) {
        if (row === m) return Math.abs(target - sum);
        if (memo[row][sum] != MAX) return memo[row][sum];
        
        let min = MAX;
        
        mat[row].sort((a, b) => a - b); 
        
        const set = new Set(mat[row]);
       
        for (const num of set) {
           const res = topDown(row + 1, sum + num);
            
           if (res > min) break;
           min = res;
        }
        
        memo[row][sum] = min;
        
        return min;
    }
};
Minimize the Difference Between Target and Chosen Elements