Untitled

class Solution {
public:
    
    pair<long, long> func(int x, int y, vector<vector<int>>& a, vector<vector<pair<long, long>>>& dp) {
        if(x < 0 || y < 0)
            return pair<long, long>(INT_MIN/3, INT_MIN/3);
        if(dp[x][y] != pair<long, long>(INT_MIN/3, INT_MIN/3))
            return dp[x][y];
        pair<long, long> val1 = func(x, y-1, a, dp);
        pair<long, long> val2 = func(x-1, y, a, dp);
        
        long pathLenFrom1 = val1.first + a[x][y];
        long pathLenFrom2 = val2.first + a[x][y];
        long minValIfComingFromPath1 = min(val1.second, pathLenFrom1);
        long minValIfComingFromPath2 = min(val2.second, pathLenFrom2);
        pair<long, long> ans;
        if(minValIfComingFromPath1 == minValIfComingFromPath2) {
            ans = pair<long, long>(max(pathLenFrom1, pathLenFrom2), minValIfComingFromPath1);
        }else if(minValIfComingFromPath1 > minValIfComingFromPath2){
            ans = pair<long, long>(pathLenFrom1, minValIfComingFromPath1);
        }else {
            ans = pair<long, long>(pathLenFrom2, minValIfComingFromPath2);
        }
        dp[x][y] = ans;
        return ans;
    }
    
    int calculateMinimumHP(vector<vector<int>>& a) {
        long inf = INT_MIN/3;
        int m = a.size();
        int n = a[0].size();
        vector<vector<pair<long, long>>> dp(m+5, vector<pair<long, long>>(n+5, pair<long, long>(inf, inf)));
        dp[0][0] = pair<long, long>(a[0][0], a[0][0]);
        auto ans = func(m-1, n-1, a, dp);
        int min_val = ans.second;
        if(min_val > 0)
            return 1;
        return -1*min_val + 1;
    }
};