本题本质上是一个 带资源约束的有向无环图（DAG）最长路径问题，可以通过 动态规划 求解。

1. 问题建模

我们将表世界和里世界的每一个位置视为状态节点。

• 状态空间：共有 个节点。 表示表世界第 个点， 表示里世界第 个点。
• 初始状态： 为起点，初始收益为 。 不可作为起点。
• 边的定义（从 到 ）：
  1. 同世界行走（Walk）：无条件转移。
     • ，收益增加 。
     • ，收益增加 。
  2. 跨世界跃迁（Warp）：有条件转移。
     • ，条件：当前持有金币 ；收益变化：。
     • ，条件：当前持有金币 ；收益变化：。

2. 核心约束

• 资源门槛：通过边的条件依赖于累积的路径权重（金币数）。通常这类问题需要将资源量作为DP的一个维度，但由于金币数量高达 （），无法将其纳入状态下标。
• 最优子结构性质：如果是最小化问题，可能存在“为了保留跃迁能力而故意不捡金币”的权衡；但本题目标是最大化金币。由于金币数量非负且越多越好（既增加了最终得分，也增加了跨越门槛 的可能性），因此满足由局部最优推导全局最优的贪心性质。

算法：线性动态规划

鉴于移动方向是单向的（从 到 ），且当前状态仅依赖于上一位置的状态，我们可以采用线性动态规划。

1. 状态定义

我们需要维护到达每一个位置时可能持有的最大金币数。 设 表示到达 表世界 第 个点时所持有的最大金币数。 设 表示到达 里世界 第 个点时所持有的最大金币数。

如果某个状态不可达（例如无法支付 进行跃迁，或者起点限制），我们将其标记为 。

2. 状态转移方程

对于位置 ()，其状态由 转移而来：

A. 计算表世界状态 （来源：表世界行走 或 里世界跃迁）

注意：如果不满足 ，则第二项不参与比较（视为 ）。

B. 计算里世界状态 （来源：里世界行走 或 表世界跃迁）

注意：如果不满足 ，则第二项不参与比较。

代码实现

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

static constexpr ll INF = -1e18;

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

    int n;
    ll k;
    cin >> n >> k;
    vector<ll> a(n);
    vector<ll> b(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> b[i];

    vector<vector<ll>> dp(n, vector<ll>(2, INF));
    dp[0][0] = a[0];
    dp[0][1] = INF;

    for (int i = 1; i < n; i++) {
        // 计算到达表世界 i 的最大值
        ll X = dp[i - 1][0] + a[i];
        ll Y = INF;
        if (dp[i - 1][1] >= k)
            Y = dp[i - 1][1] - k + a[i];
        dp[i][0] = max(X, Y);

        // 计算到达里世界 i 的最大值
        ll P = dp[i - 1][1] + b[i];
        ll Q = INF;
        if (dp[i - 1][0] >= k)
            Q = dp[i - 1][0] - k + b[i];
        dp[i][1] = max(P, Q);
    }

    ll ans = max(dp[n - 1][0], dp[n - 1][1]);
    cout << ans << endl;
}