题解

题意重述：时间轴从 $0$ 到 $X$。司机在时刻 $kT$（$k=0,1,2,\dots$）需要 $1$ 升水，$M$ 名乘客 $j$ 在时刻 $kT+D_j$（$k=0,1,2,\dots$）需要 $1$ 升水，其中 $1\le D_j<T$ 且 $D_j$ 两两不同。可在时刻 $0$ 与所有服务站时刻 $S_i$ 加水（每升费用恒为 $W$，水箱无限大）。若某乘客在到终点前的某次需求没有水，则立刻下车并需赔偿 $C_j$；司机若没水则无法继续行驶（必须保证永远有水）。且保证所有服务站与终点时刻不与任何喝水时刻重合，不会有两人同时需要水。目标是最小化“购水总费用 + 退款总费用”。

关键化简：价格恒为每升 $W$，且可在服务站无限补给，因此“何时购入”不影响总成本，只需决定“哪些喝水事件需要满足”。

• 司机的所有喝水事件必须满足，次数为 $\#\{k\mid 0\le kT<X\}=\left\lfloor\dfrac{X-1}{T}\right\rfloor+1$，对应固定费用 $W$ 乘以该次数。
• 对于乘客 $j$，一旦某次未能供水，他立刻下车，此后不再产生需求。显然最优策略要么“从第一次需求起次次都满足”（全程保留该乘客），要么“第一次需求就让其下车”（立即退款），中途先供后弃只会更劣。
• 乘客 $j$ 在 $[0,X)$ 内的喝水次数为 $\#\{k\mid 0\le k,\ D_j+kT<X\}=\left\lfloor\dfrac{X-1-D_j}{T}\right\rfloor+1$。若全程保留他，则增添的购水成本为 $W\cdot \left(\left\lfloor\dfrac{X-1-D_j}{T}\right\rfloor+1\right)$；若不保留，则一次性支付 $C_j$。二者取较小即为该乘客的最优贡献。

由此，总最小费用为：

$$\mathrm{Ans} = W\cdot\Big(\left\lfloor\tfrac{X-1}{T}\right\rfloor+1\Big) \;+ \sum_{j=1}^{M} \min\!\left(\,C_j,\; W\cdot\Big(\left\lfloor\tfrac{X-1-D_j}{T}\right\rfloor+1\Big)\right). $$

正确性说明：

• 由于水价对所有时刻恒定，且容量无限，任一给定的“被满足的喝水事件集合”都能通过在各服务站按需采购来实现，中途不会因“采购时机”而更优或更劣；因此只需在“事件级别”上做选择。
• 对任一乘客，若在他第一次需求时不供水，立即下车可避免后续所有购水；若先满足若干次后再让其下车，则既产生了前面的购水费用，又仍需支付同样的退款 $C_j$，显然不优。
• 司机必须全程被满足，否则不可行。

实现与复杂度：

• 预处理司机次数与每个乘客的次数即可，直接代入上式求和。
• 时间复杂度 $O(M)$，空间 $O(1)$（不计输入）。

注意事项：题目保证任何喝水时刻与任一服务站或终点不重合，且不同人的喝水时刻互不碰撞，上述计数公式可直接使用；同时无需担心“区间内水量不足”，因为可在每个区间起点按需一次性补足。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5, inf = 7e18;
int X, n, m, W, T;
pair<int, int>s[N], a[N];
int sm[N];
int dp[N];
int tx[N], ty[N];
int stk[N], top;
void ins(int x) {
    while (top > 1 &&
            (ty[x] - ty[stk[top]]) * (tx[stk[top]] - tx[stk[top - 1]]) <= (ty[stk[top]] - ty[stk[top - 1]]) *
            (tx[x] - tx[stk[top]]))
        --top;

    stk[++top] = x;
}
int query(int k) {
    int l = 2, r = top, ans = 1, mid = 0;

    while (l <= r) {
        mid = (l + r) >> 1;

        if (ty[stk[mid]] - ty[stk[mid - 1]] < k * (tx[stk[mid]] - tx[stk[mid - 1]]))
            ans = mid, l = mid + 1;
        else
            r = mid - 1;
    }

    return stk[ans];
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> X >> n >> m >> W >> T;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        s[i] = {x % T, x};
    }

    s[++n] = {X % T, X};

    for (int i = 1; i <= m; i++)
        cin >> a[i].first >> a[i].second;

    sort(s + 1, s + 1 + n);
    sort(a + 1, a + 1 + m);
    a[m + 1].first = inf;

    for (int i = 1; i <= m; i++)
        sm[i] = sm[i - 1] + a[i].second;

    int p = 1;
    ins(0);

    for (int i = 1; i <= m; i++) {
        dp[i] = dp[i - 1] + W * (X / T + (X % T >= a[i].first));
        int mn = inf;

        while (p <= n && s[p].first < a[i].first)
            ++p;

        while (p <= n && s[p].first < a[i + 1].first)
            mn = min(mn, s[p].second / T), ++p;

        if (mn < inf) {
            int j = query(W * mn);
            dp[i] = min(dp[i], dp[j] + sm[i] - sm[j] + W * (i - j) * mn);
        }

        tx[i] = i, ty[i] = dp[i] - sm[i];
        ins(i);
    }

    cout << dp[m] + W * (X / T + 1) << '\n';
    return 0;
}