From formula not intuition
Lots of people can\'t understand the intuition. But it\'s ok. We can always figure out the formula to get the ans.\nAssume  diff_j = cost_j - cashback_j, x - su
Lots of people can\'t understand the intuition. But it\'s ok. We can always figure out the formula to get the ans.\nAssume  diff_j = cost_j - cashback_j, x - sum(diff_j) >= cost_i always be true for all i. (j = 0, 1, 2 ... i-1)\n=> we can get: x >= cost_i + sum(diff_i)\n=> x >= max((cost_i) + sum(diff_i))\n=> we transfer the problem to calculate the max(cost_i + sum(diff_i)) => max(cost_i) + max(sum(diff_j)) = res\n\nLet\'s solve this max(cost_i + sum(diff_i)) case by case.\ncase 1: max(cost_i) is from diff_i >= 0\nres = sum of diffs (that all diff >= 0) - (cost_i - cashback_i) + cost_i\nres = sum of diffs (that all diff >= 0) + cashback_i\nwhich means we need to find the max cashback among all diffs that diff > 0.\n\ncase2: max(cost_i) is from diff_i < 0\nres = sum of diffs (that all diff >= 0) + max(cost_i). (cost_i from the diff_i that diff_i < 0)\n\nfinal res = Math.max(case1, case2)\n```\nclass Solution {\n    public long minimumMoney(int[][] transactions) {\n        int n = transactions.length;\n        long maxCost = 0;\n        long maxCashBack = 0;\n        long sum = 0;\n        for (int[] t: transactions) {\n            int cost = t[0];\n            int back = t[1];\n            if (cost - back > 0) {\n                sum += (long)(cost - back);\n                maxCashBack = Math.max(maxCashBack, back);\n            } else {\n                maxCost = Math.max(cost, maxCost);\n            }\n        }\n        return sum + Math.max(maxCashBack, maxCost);\n    }\n}\n```
['Math', 'Greedy']