概要

この問題は、スタート地点 \(1\) からゴール地点 \(N\) まで、スタミナが \(0\) 未満にならないように移動経路と補給食を食べるタイミングを最適化し、最終的なスタミナを最大化する問題です。

一見、補給食をいつ食べるかの選択肢が多くて複雑に見えますが、「スタミナの上限がない」という性質を利用することで、シンプルな動的計画法（DP）に帰着させることができます。

---

考察

1. 補給食を食べるタイミングの単純化

この問題の最も重要なポイントは、「スタミナに上限がない」ということです。

スタミナに上限がないため、補給食を温存するメリットはありません。ある地点で補給食を食べてスタミナを増やしておくのも、後で食べるのも、最終的なスタミナの合計値は変わりません。むしろ、途中でスタミナが \(0\) 未満になってリタイアするのを防ぐためには、手に入れた補給食は次の移動の直前までにすべて食べてしまい、常にスタミナを最大に保っておくのが常に最善（最適戦略）となります。

したがって、以下のように単純化して考えることができます。 * 地点 \(i\) から次の地点へ移動する直前に、地点 \(i\) で入手した補給食も含め、手持ちの補給食をすべて食べる。

2. 動的計画法（DP）への適用

移動の選択肢は「\(1\) つ先の地点への移動」または「\(2\) つ先の地点への移動」の \(2\) 通りです。 各地点に到達した時点でのスタミナの最大値を管理しながら進めるために、以下のDPテーブルを定義します。

• dp[i] ： 地点 \(i\) に到達し、消耗度 \(H_i\) による減少を受けた直後（地点 \(i\) の補給食を食べる前）のスタミナの最大値。到達不可能な場合は \(-\infty\) とします。

地点 \(i\) に到達した直後、生存判定（スタミナが \(0\) 以上か）を行います。生存していれば、その地点にある補給食 \(R_i\) を食べることができるため、次の移動の直前にはスタミナは dp[i] + R[i] まで回復します。

---

アルゴリズム

DPの初期値

• 地点 1: 初期スタミナ \(K\) から地点 \(1\) の消耗度 \(H_1\) を引きます。 \(K - H_1 \ge 0\) であれば、 dp[1] = K - H_1 となります。未満であれば、スタート直後にリタイアとなるため到達不可能です。
• 地点 2: 地点 \(2\) へは地点 \(1\) からのみ遷移できます。 地点 \(1\) で補給食を食べた後のスタミナは dp[1] + R[1] です。ここから地点 \(2\) に移動すると \(H_2\) 消耗するため、 dp[1] + R[1] - H[2] >= 0 であれば dp[2] = dp[1] + R[1] - H[2] となります。

DPの遷移（\(3 \le i \le N\)）

地点 \(i\) へは、地点 \(i-1\) または地点 \(i-2\) から移動してくることができます。

1. 地点 \(i-1\) からの遷移: 移動直前のスタミナは dp[i-1] + R[i-1] です。地点 \(i\) に移動すると \(H_i\) 消耗するため、移動後のスタミナは以下になります。 $\(val_1 = dp[i-1] + R[i-1] - H_i\)$
2. 地点 \(i-2\) からの遷移: 同様に、移動後のスタミナは以下になります。 $\(val_2 = dp[i-2] + R[i-2] - H_i\)$

これら \(2\) つの遷移のうち、大きい方を採用します。 $\(mx = \max(val_1, val_2)\)\( この \)mx\( が \)0\( 以上であれば、地点 \)i\( に生存して到達できるため `dp[i] = mx` と更新します。\)0\( 未満であれば到達不可能です（\)-\infty$ のままにします）。

最終的な答え

地点 \(N\) に到達した直後のスタミナの最大値は dp[N] です。 最後に、地点 \(N\) にある補給食 \(R_N\) をすべて食べ終えた時点でのスタミナが最大値となるため、求める答えは dp[N] + R[N] となります。 （もし dp[N] が \(-\infty\) のままであれば、地点 \(N\) に到達できないため -1 を出力します）

---

計算量

• 時間計算量: \(O(N)\) 各地点 \(i\) (\(3 \le i \le N\)) について、直前 \(2\) つの状態からの定数時間 \(O(1)\) の遷移を計算するだけであるため、全体で \(O(N)\) 時間で動作します。制約の \(N \le 10^6\) に対しても十分高速に実行可能です。

• 空間計算量: \(O(N)\) 長さ \(N+1\) のDP配列および各地点の消耗度 \(H\)、補給食の回復量 \(R\) を保持する配列を用意するため、空間計算量は \(O(N)\) となります。

---

実装のポイント

• 補給食がない地点の扱い: あらかじめサイズ \(N+1\) の配列 \(R\) を \(0\) で初期化しておき、補給食が存在する地点 \(P_j\) についてのみ \(R[P_j] = R_j\) と更新しておくことで、補給食の有無を個別に条件分岐することなく、一貫して dp[i] + R[i] という形でシンプルに実装できます。

• 到達不能の表現: 到達できない状態を正しく区別するために、初期値には十分に小さな値（\(-\infty\) として -10**18 など）を使用します。

  ソースコード

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()

---

この解説は gemini-3.5-flash-high によって生成されました。