// Algorithm / 演算法：
// 按 (minimum - actual) 由大到小排序 (greedy / exchange-argument optimal)，
// 然後掃過一次，記錄已花費 actual 之和 spent，答案 = max(spent + minimum)。
// Sort tasks by (min - actual) descending, then sweep tracking spent;
// the answer is the max of (spent_before_task + minimum) over all tasks.

#include <stdlib.h>   // 為了 qsort / for qsort

// 比較函式：a, b 都是 int*（指向 tasks[i] 那一列的指標）
// Comparator: a and b are int** pointing to a row of tasks.
// qsort 傳給我們的是「指向元素的指標」，而元素本身是 int*，所以 a 實際型別是 int**。
// qsort hands us pointers to elements; each element is an int*, so a is int**.
static int cmp(const void *a, const void *b) {
    // 解兩層指標拿到 row（int*）/ dereference once to get the row (int*)
    const int *ra = *(const int *const *)a;
    const int *rb = *(const int *const *)b;
    // slack_a = ra[1] - ra[0]；slack_b = rb[1] - rb[0]
    // 我們要 slack 大的排前面，所以回傳 slack_b - slack_a
    // We want larger slack first, so return slack_b - slack_a.
    int slack_a = ra[1] - ra[0];
    int slack_b = rb[1] - rb[0];
    return slack_b - slack_a;   // 負數代表 a 排前面 / negative means a comes first
}

// LeetCode signature：tasks 是 int**（指標的陣列，每個指向長度 2 的 int 陣列）
// LeetCode signature: tasks is int** (array of pointers, each row has length 2).
int minimumEffort(int** tasks, int tasksSize, int* tasksColSize) {
    // 原地排序 tasks（修改傳入的陣列順序）
    // Sort tasks in-place; we don't need the original order afterwards.
    qsort(tasks, tasksSize, sizeof(int *), cmp);

    long spent = 0;   // 已累計花費的 actual / running sum of actual costs
    long ans = 0;     // 目前答案下界 / current lower bound for initial energy
    // 用 long 避免極端情況下 10^5 * 10^4 = 10^9 接近 int 上限 (~2.1e9)
    // long avoids overflow risk when spent + minimum could approach 2 * 10^9.

    for (int i = 0; i < tasksSize; i++) {
        int actual  = tasks[i][0];   // 實際花費 / energy actually spent
        int minimum = tasks[i][1];   // 進入門檻 / threshold required to start
        // 開始這個任務前需要 spent + minimum 的初始能量
        // To start this task we need initial energy of at least spent + minimum.
        long need = spent + minimum;
        if (need > ans) ans = need;  // 取最大值 / take the max constraint
        spent += actual;             // 做完後累加實際花費 / accumulate actual after finishing
    }
    return (int)ans;   // 題目保證落在 int 範圍內 / answer fits in int
}