Overview

We travel from point \(1\) to point \(N\), moving by \(+1\) or \(+2\) at each step.
At each point, stamina is consumed, and if food is available, it can be recovered. We use dynamic programming to find the maximum stamina with which we can reach the destination without retiring.

Analysis

An important point in this problem is that there is no disadvantage in eating food as soon as you obtain it.

There is no upper limit on stamina. Therefore, rather than saving the food for later, eating it immediately to increase stamina makes it less likely to retire at subsequent points.
Additionally, since our goal is to maximize the stamina after reaching point \(N\) and eating all remaining food, the total amount of recovery remains the same whether we eat it along the way or at the end.

Therefore, when reaching each point, we can assume:

1. Decrease stamina by the consumption \(H_i\) at that point.
2. If stamina is less than \(0\), we fail (retire).
3. If there is food, obtain it and eat it immediately.

This simplification is perfectly valid.

---

If we naively try all possible paths, the number of paths grows exponentially because we have a choice of \(+1\) or \(+2\) at each point.
Since \(N\) is at most \(10^6\), an exhaustive search will not run in time.

Therefore, for each point \(i\), we keep track of:

The maximum stamina after reaching point \(i\) and eating the food at that point.

Let this value be \(dp[i]\).

The point immediately before point \(i\) must be either \(i-1\) or \(i-2\).
Therefore, we can transition from \(dp[i-1]\) or \(dp[i-2]\).

However, because the consumption \(H_i\) is subtracted the moment we reach point \(i\), the stamina before reaching must be at least \(H_i\).

For example, if we come from point \(i-1\):

• If \(dp[i-1] \geq H_i\), it is reachable.
• The stamina after reaching is \(dp[i-1] - H_i\).
• After that, if there is food, we recover \(R_i\).

Thus,

\[ dp[i] = dp[i-1] - H_i + R_i \]

becomes a candidate.

Similarly, we consider the case of coming from point \(i-2\) and take the larger of the two.

Algorithm

First, we record the recovery amount of food at each point in an array \(R\).
For points without food, we set \(R_i = 0\).

We define \(dp[i]\) as follows:

\[ dp[i] = \text{the maximum stamina after reaching point } i \text{ and eating the food there} \]

If a point is unreachable, we set \(dp[i] = -1\).

Initialization

We start from point \(1\).
Since we immediately suffer the consumption \(H_1\) at point \(1\):

• If \(K \geq H_1\), it is reachable.
• After that, if there is food, we recover.

Therefore,

\[ dp[1] = K - H_1 + R_1 \]

If \(K < H_1\), we retire at the very first point, so \(dp[1]\) remains \(-1\).

Transitions

For point \(i\), the immediately preceding point is either \(i-1\) or \(i-2\).

When coming from point \(i-1\):

\[ dp[i-1] \geq H_i \]

If this holds, it is reachable, and we can transition as:

\[ dp[i] = \max(dp[i], dp[i-1] - H_i + R_i) \]

When coming from point \(i-2\):

\[ dp[i-2] \geq H_i \]

If this holds, it is reachable, and we can transition as:

\[ dp[i] = \max(dp[i], dp[i-2] - H_i + R_i) \]

Finally, \(dp[N]\) is the answer.
If it is unreachable, \(dp[N]\) will be \(-1\).

Complexity

• Time Complexity: \(O(N + M)\)
• Space Complexity: \(O(N)\)

Implementation Points

• It is convenient to store the food information in an array \(R\) indexed by the point number.

• Stamina, consumption, and recovery values can be up to \(10^9\), and their sum can become large. Therefore, use long long.

• Use \(dp[i] = -1\) to represent “unreachable”.

• Since point \(2\) cannot be reached from point \(0\), the transition from \(i-2\) should only be performed when \(i \geq 3\).

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    long long K;
    cin >> N >> M >> K;

    vector<long long> H(N + 1), R(N + 1, 0);
    for (int i = 1; i <= N; i++) cin >> H[i];

    for (int j = 0; j < M; j++) {
        int P;
        long long r;
        cin >> P >> r;
        R[P] = r;
    }

    vector<long long> dp(N + 1, -1);

    if (K >= H[1]) {
        dp[1] = K - H[1] + R[1];
    }

    for (int i = 2; i <= N; i++) {
        long long best = -1;

        if (dp[i - 1] >= H[i]) {
            best = max(best, dp[i - 1] - H[i] + R[i]);
        }

        if (i >= 3 && dp[i - 2] >= H[i]) {
            best = max(best, dp[i - 2] - H[i] + R[i]);
        }

        dp[i] = best;
    }

    cout << dp[N] << '\n';

    return 0;
}

---

This editorial was generated by gpt-5.5-high.