Overview

This problem asks you to determine whether you can reach the end by managing your battery level as it decreases while traveling through each segment, and appropriately choosing whether to “swap or not” at charging stations along the way.

Analysis

Key Insight

At charging station \(j\), you cannot increase the battery to any arbitrary value — you can only swap to make it exactly \(S_j\).
Therefore, the optimal action at each station is very simple:

• When the current battery level is \(b\):
  • If \(S_j \le b\), swapping would actually decrease (or maintain) the level, so not swapping is better
  • If \(S_j > b\), swapping increases the level, so swapping is better

In other words, the optimal action at each station is “\(b \leftarrow \max(b, S_j)\)”.

Why This Greedy Approach Is Correct

Whether you swap at a station affects your ability to travel further, but the resulting battery level after swapping is fixed at \(S_j\).
Therefore, “swapping” simply means “overwriting the battery level with \(S_j\)”, and strategies like conserving for the future or charging incrementally do not exist.

Thus, there is no benefit other than increasing the level when possible (swap if \(S_j > b\)), and the locally optimal choice directly becomes the globally optimal choice.

Why a Naive Approach Is Difficult

If you “try all combinations of swapping/not swapping at each station,” there are up to \(2^M\) possibilities, which is far too slow for \(M \le 2 \times 10^5\).
However, due to the observation above, the decision at each station is uniquely determined, and a simple simulation is sufficient.

Algorithm

1. Initialize the current battery level \(b\) to \(K\).
2. Process segments \(i = 1, 2, \dots, N\) in order.
   • Before traveling segment \(i\), if \(b \ge 1\) does not hold, you cannot travel, so output No.
   • Travel segment \(i\): \(b \leftarrow b - D_i\).
   • If there is a station “between segments \(i\) and \(i+1\)” (i.e., \(P_j = i\)), then:
     • \(b \leftarrow \max(b, S_j)\) (swap only when it increases the level)
3. If all segments are processed successfully, output Yes.

Paying attention to the meaning of positions, station \(j\) can be used “immediately after finishing segment \(P_j\) (just before segment \(P_j + 1\))”, so the correct approach is to check after subtracting \(D_{P_j}\).

Example (Illustration)

• At some point \(b = 3\), and the next station has \(S_j = 10\): swapping to \(b = 10\) is beneficial.
• Conversely, \(b = 8\) and \(S_j = 5\): swapping would make \(b = 5\), which is a loss, so don’t swap.

Complexity

• Time complexity: \(O(N + M)\) (each segment is processed once, and each station is processed once using a pointer)
• Space complexity: \(O(N + M)\) (for storing input; the simulation itself requires \(O(1)\) additional space)

Implementation Notes

• The condition for being able to travel is that \(b \ge 1\) before traveling (even if the battery drops to \(0\) or below after traveling, the segment itself is considered successfully traveled).

• Since stations are in ascending order \(P_1 < P_2 < \cdots\), you can process them in \(O(N + M)\) by advancing a pointer \(j\) and checking P[j] == i.

• The timing for processing a station should be placed after \(b -= D[i-1]\) (immediately after segment \(i\)).

  Source Code

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    M = next(it)
    K = next(it)

    D = [next(it) for _ in range(N)]
    P = [0] * M
    S = [0] * M
    for j in range(M):
        P[j] = next(it)
        S[j] = next(it)

    b = K
    j = 0
    for i in range(1, N + 1):
        if b < 1:
            print("No")
            return
        b -= D[i - 1]
        if j < M and P[j] == i:
            if S[j] > b:
                b = S[j]
            j += 1

    print("Yes")

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.