Overview

This problem asks us to find an optimal route from the starting point \(1\) to the goal \(N\), along with the optimal timing to consume rations, such that our stamina never falls below \(0\) and the final stamina is maximized.

At first glance, the choices of when to eat the rations may seem numerous and complex. However, by utilizing the property that “there is no upper limit on stamina,” we can reduce this problem to a simple Dynamic Programming (DP) approach.

---

Observations

1. Simplifying the Timing of Eating Rations

The most crucial point of this problem is that “there is no upper limit on stamina.”

Since there is no upper limit on stamina, there is no advantage in saving rations for later. Whether you eat a ration at a certain point to increase your stamina now, or eat it later, the final total stamina remains the same. In fact, to prevent the stamina from dropping below \(0\) and retiring along the way, the optimal strategy is always to eat all available rations immediately before the next move, keeping the stamina as high as possible at all times.

Therefore, we can simplify our thinking as follows: * Immediately before moving from point \(i\) to the next point, eat all rations currently held, including the ration obtained at point \(i\).

2. Applying Dynamic Programming (DP)

There are two possible moves: “moving to the next point” or “moving to the point after next.” To keep track of the maximum stamina upon reaching each point, we define the following DP table:

• dp[i] : The maximum stamina immediately after reaching point \(i\) and suffering the stamina loss from exhaustion \(H_i\) (before eating the ration at point \(i\)). If point \(i\) is unreachable, this value is \(-\infty\).

Immediately upon reaching point \(i\), we check for survival (whether stamina is \(0\) or greater). If we survive, we can eat the ration \(R_i\) at that point, so the stamina recovers to dp[i] + R[i] right before the next move.

---

Algorithm

DP Initialization

• Point 1: Subtract the exhaustion \(H_1\) of point \(1\) from the initial stamina \(K\). If \(K - H_1 \ge 0\), then dp[1] = K - H_1. If it is less than \(0\), we retire immediately after starting, making it unreachable.
• Point 2: Point \(2\) can only be reached from point \(1\). The stamina after eating the ration at point \(1\) is dp[1] + R[1]. Moving to point \(2\) from here consumes \(H_2\) stamina. Thus, if dp[1] + R[1] - H[2] >= 0, then dp[2] = dp[1] + R[1] - H[2].

DP Transitions (\(3 \le i \le N\))

We can move to point \(i\) from either point \(i-1\) or point \(i-2\).

1. Transition from point \(i-1\): The stamina immediately before moving is dp[i-1] + R[i-1]. Moving to point \(i\) consumes \(H_i\) stamina, so the stamina after the move is: $\(val_1 = dp[i-1] + R[i-1] - H_i\)$
2. Transition from point \(i-2\): Similarly, the stamina after the move is: $\(val_2 = dp[i-2] + R[i-2] - H_i\)$

We take the maximum of these two transitions: $\(mx = \max(val_1, val_2)\)\( If \)mx \ge 0\(, we can successfully reach point \)i\( alive, so we update `dp[i] = mx`. If it is less than \)0\(, point \)i\( is unreachable (it remains \)-\infty$).

Final Answer

The maximum stamina immediately after reaching point \(N\) is dp[N]. Finally, the stamina after consuming all rations \(R_N\) at point \(N\) will be the maximum possible stamina, so the answer is dp[N] + R[N]. (If dp[N] remains \(-\infty\), point \(N\) is unreachable, so we output -1.)

---

Complexity

• Time Complexity: \(O(N)\) For each point \(i\) (\(3 \le i \le N\)), we only need to compute transitions from the previous two states in constant \(O(1)\) time, so the algorithm runs in \(O(N)\) time overall. This is sufficiently fast even for the constraint \(N \le 10^6\).

• Space Complexity: \(O(N)\) Since we allocate a DP array of size \(N+1\), as well as arrays to store the exhaustion \(H\) and ration recovery amount \(R\) for each point, the space complexity is \(O(N)\).

---

Implementation Details

• Handling points without rations: By initializing an array \(R\) of size \(N+1\) with \(0\) beforehand, and updating \(R[P_j] = R_j\) only for points \(P_j\) where rations exist, we can implement the transition simply as dp[i] + R[i] without needing conditional branching for whether a ration is present at each point.

• Representing Unreachability: To correctly distinguish unreachable states, use a sufficiently small value as the initial value (such as -10**18 representing \(-\infty\)).

  Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    H = [0] + [int(x) for x in input_data[3:3+N]]
    
    R = [0] * (N + 1)
    idx = 3 + N
    for _ in range(M):
        p = int(input_data[idx])
        r = int(input_data[idx+1])
        R[p] = r
        idx += 2
        
    INF = 10**18
    dp = [-INF] * (N + 1)
    
    if K - H[1] >= 0:
        dp[1] = K - H[1]
        
    if dp[1] != -INF:
        val = dp[1] + R[1] - H[2]
        if val >= 0:
            dp[2] = val
            
    for i in range(3, N + 1):
        val1 = dp[i-1] + R[i-1] - H[i] if dp[i-1] != -INF else -INF
        val2 = dp[i-2] + R[i-2] - H[i] if dp[i-2] != -INF else -INF
        mx = max(val1, val2)
        if mx >= 0:
            dp[i] = mx
            
    if dp[N] == -INF:
        print(-1)
    else:
        print(dp[N] + R[N])

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3.5-flash-high.