Overview

We determine whether it is possible to travel from point \(1\) to point \(N\) by moving either \(+1\) or \(+2\) at each step without our stamina becoming negative.
There is no need to worry about the optimal timing to eat rations. We can manage the maximum stamina at each reachable point using dynamic programming.

Intuition

The key to this problem is deciding when to eat the rations.

The order of processing at each point is:

1. Depletion (stamina consumption)
2. Retirement check (game over check)
3. Obtaining the ration
4. Using the ration

This means that when arriving at point \(i\), the ration at point \(i\) cannot be used yet.
Therefore, the condition to reach point \(i\) is that the stamina before arriving must be at least \(H_i\).

On the other hand, once a ration is obtained, there is no benefit in delaying when to eat it.

The reasons are as follows:

• There is no upper limit on stamina.
• Eating rations early does not cause any disadvantage.
• The more stamina you have, the easier it is to reach subsequent points.
• Ultimately, we want to maximize the stamina after eating all remaining rations.

Therefore, we do not lose the optimal solution by assuming that we “eat any obtained ration immediately.”

This simplifies the state we need to maintain significantly.

Let \(dp[i]\) be:

the maximum stamina after reaching point \(i\) and eating all rations obtained up to that point.

To reach point \(i\), we can come from either point \(i-1\) or point \(i-2\).
However, if the stamina becomes negative immediately after suffering the depletion of \(H_i\) at point \(i\), we retire. Thus, the stamina at the starting point of the transition must be at least \(H_i\).

For example, when coming from point \(i-1\):

• The stamina after processing point \(i-1\) is \(dp[i-1]\).
• Stamina decreases by \(H_i\) due to depletion at point \(i\).
• If we survive, we obtain and immediately eat the ration \(R_i\) at point \(i\).

Thus, we have:

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

Note that this is only possible if \(dp[i-1] \geq H_i\).

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

If we naively try all possible paths, the number of paths grows exponentially because we have a choice of moving \(+1\) or \(+2\) at each point.
Additionally, deciding when to eat the rations would make it even more complex.

However, since we can assume rations are “eaten immediately upon acquisition,” it is sufficient to manage only the maximum stamina at each point.

Algorithm

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

The starting point is point \(1\).

Upon arriving at point \(1\), we first consume \(H_1\) stamina.
If

\[ K < H_1 \]

we retire at the very first point, so the answer is \(-1\).

Otherwise, the stamina after processing point \(1\) is:

\[ K - H_1 + R_1 \]

Thereafter, we calculate the values for point \(2\) to point \(N\) in order.

For point \(i\), we check the following:

• Whether we can come from point \(i-1\)
• Whether we can come from point \(i-2\)

When coming from point \(i-1\), it is reachable if \(dp[i-1] \geq H_i\), and we get:

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

When coming from point \(i-2\), it is reachable if \(dp[i-2] \geq H_i\), and we get:

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

We take the maximum of these as \(dp[i]\).
If we cannot reach from either, we mark the point as unreachable by setting it to \(-1\).

Also, the transitions only require the two most recent values.
Therefore, we can update them by keeping only:

• dp_prev2: \(dp[i-2]\)
• dp_prev1: \(dp[i-1]\)

instead of maintaining the entire array.

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

Complexity

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

Key Implementation Points

It is convenient to store the ration information in an array R of length \(N\).

R = [0] * N
for _ in range(M):
    p, r = map(int, input().split())
    R[p - 1] = r  # Adjust 1-based index to 0-based index

Note that the point indices in the input are 1-based, but Python arrays are 0-based, so we use p - 1.

Also, we represent unreachable states with -1.
Since we can survive as long as stamina is at least \(0\), -1 can be safely used as a sentinel value.

In the transition, the stamina before entering point \(i\) must be at least \(H_i\).

if dp_prev1 >= h:
    best = dp_prev1 - h + R[i]

if dp_prev2 >= h:
    cand = dp_prev2 - h + R[i]
    best = max(best, cand)

Finally, we perform rolling updates.

dp_prev2, dp_prev1 = dp_prev1, best

This allows us to perform the calculation without storing the entire DP array.

Source Code

import sys

def main():
    input = sys.stdin.buffer.readline

    N, M, K = map(int, input().split())
    H = list(map(int, input().split()))

    R = [0] * N
    for _ in range(M):
        p, r = map(int, input().split())
        R[p - 1] = r

    if K < H[0]:
        print(-1)
        return

    dp_prev2 = -1
    dp_prev1 = K - H[0] + R[0]

    for i in range(1, N):
        h = H[i]
        best = -1

        if dp_prev1 >= h:
            best = dp_prev1 - h + R[i]

        if dp_prev2 >= h:
            cand = dp_prev2 - h + R[i]
            if cand > best:
                best = cand

        dp_prev2, dp_prev1 = dp_prev1, best

    print(dp_prev1)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.