#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define llint long long #define inf 1e18 #define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++) #define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++) #define chmin(x, y) (x) = min((x), (y)) #define chmax(x, y) (x) = max((x), (y)) #define mod 1000000007 using namespace std; typedef pair P; struct edge{ llint to, cost; edge(){} edge(llint a, llint b){ to = a, cost = b; } }; llint n, k; llint a[100005], b[100005]; vector G[100005]; llint dist[100005]; void dijkstra(vector G[], llint S, llint dist[]) { for(int i = 1; i <= n; i++) dist[i] = inf; dist[S] = 0; priority_queue< P, vector

, greater

> Q; Q.push( make_pair(0, S) ); llint v, d; while(Q.size()){ d = Q.top().first; v = Q.top().second; Q.pop(); if(dist[v] < d) continue; for(int i = 0; i < G[v].size(); i++){ if(dist[G[v][i].to] > d + G[v][i].cost){ dist[G[v][i].to] = d + G[v][i].cost; Q.push( make_pair(dist[G[v][i].to], G[v][i].to) ); } } } } int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> k; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= n; i++) cin >> b[i]; for(int i = 2; i <= n; i++){ if(i-2 >= 1) G[i-2].push_back(edge(i, a[i-2]+b[i]+k)); G[i-1].push_back(edge(i, a[i-1]+b[i])); } dijkstra(G, 1, dist); llint ans = 0; for(int i = 1; i <= n; i++) ans = max(ans, dist[i]); cout << ans << endl; return 0; }