#define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; #define REP(i, n) for(ll i=0; i<(n);i++) #define VL vector template vector read(size_t n) { vector ts(n); for (size_t i = 0; i < n; i++) cin >> ts[i]; return ts; } template void read_tuple_impl(TV&) {} template void read_tuple_impl(TV& ts) { get(ts).emplace_back(*(istream_iterator(cin))); read_tuple_impl(ts); } template decltype(auto) read_tuple(size_t n) { tuple...> ts; for (size_t i = 0; i < n; i++) read_tuple_impl(ts); return ts; } class Dijkstra { public: Dijkstra(ll n) { size = n; edges.resize(n); dist0.resize(n); rev.resize(n); } void addEdge(ll from, ll to, ll cost = 0) { edges[from].push_back({ to,cost }); } void SetDefaultDist(ll s) { dist0.assign(size, LLONG_MAX); rev.assign(size, -1); dist0[s] = 0; que.push(P(0, s)); } void CalcDist() { while (!que.empty()) { P p = que.top(); que.pop(); ll v = p.second; if (dist0[v] < p.first) continue; for (ll i = 0; i < edges[v].size(); i++) { edge e = edges[v][i]; if (dist0[e.to] > dist0[v] + e.cost) { dist0[e.to] = dist0[v] + e.cost; rev[e.to] = v; que.push(P(dist0[e.to], e.to)); } } } } void GetDist(ll s) { SetDefaultDist(s); CalcDist(); } ll size; // 点数 struct edge { ll to, cost; }; typedef pair P; priority_queue, greater

> que; vector> edges; vector dist0; vector rev; }; int main() { ll n, m, c; cin >> n >> m >> c; VL a = read(n); auto [l, r] = read_tuple(m); ll sumA = 0; REP(i, n) sumA += a[i]; Dijkstra dj(n + 1); REP(i, n) { dj.addEdge(i, i + 1, a[i]); dj.addEdge(i + 1, i, a[i]); } REP(i, m) { dj.addEdge(l[i] - 1, r[i], c); dj.addEdge(r[i], l[i] - 1, c); } dj.GetDist(0); cout << sumA - dj.dist0[n] << "\n"; return 0; }