求める値は、以下のようなグラフにおける頂点 \(0\) から頂点 \(N\) への最短経路に等しいです。

• 頂点は \(0, \dots, N\) の \(N + 1\) 個である。
• \(i = 1, \dots, N\) について、頂点 \(i - 1\) から頂点 \(i\) へ向かって張られた重み \(A_i\) の辺が存在する。この辺を通ることは、\(i\) 巻目を買うことに対応する。
• \(i = 1, \dots, M\) について、頂点 \(L_i - 1\) から頂点 \(R_i\) ヘ向かって張られた重み \(B_i\) の辺が存在する。この辺を通ることは、\(i\) 種類目のセットを買うことに対応する。
• \(i = 1, \dots, N\) について、頂点 \(i\) から頂点 \(i - 1\) へ向かって張られた重み \(0\) の辺が存在する。この辺は、複数のセットを買うことで生じる、同一の漫画の重複を処理するためのものである。

頂点 \(0\) から頂点 \(N\) へ移動するとき、通った辺に対応する買い方により、全ての漫画を揃えることができます。
また、全ての漫画を揃えるような買い方には、必ず頂点 \(0\) から頂点 \(N\) への経路が対応します。例えば、一つ目の入出力例の最適な買い方に対応する経路は、頂点 \(0 \rightarrow\) 頂点 \(2 \rightarrow\) 頂点 \(1 \rightarrow\) 頂点 \(4 \rightarrow\) 頂点 \(5\) となります。

ダイクストラ法を用いることで、この問題を \(O((N + M) \log N)\) で解くことができます。

実装例 (C++)

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

using ll = long long;

template <class T>
using min_heap = priority_queue<T, vector<T>, greater<>>;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<vector<pair<int, int>>> list(n);
    for (int i = 0; i < m; ++i) {
        int b, l, r;
        cin >> b >> l >> r;
        list[l - 1].emplace_back(r, b);
    }
    vector<ll> dist(n + 1, numeric_limits<ll>::max());
    min_heap<pair<ll, int>> heap;
    const auto push = [&](const int u, const ll d) {
        if (dist[u] > d) {
            dist[u] = d;
            heap.emplace(d, u);
        }
    };
    push(0, 0);
    while (!heap.empty()) {
        const auto [d, u] = heap.top();
        heap.pop();
        if (u == n) {
            break;
        }
        if (d > dist[u]) {
            continue;
        }
        push(u + 1, d + a[u]);
        if (u > 0) {
            push(u - 1, d);
        }
        for (const auto& [v, c] : list[u]) {
            push(v, d + c);
        }
    }
    cout << dist[n] << '\n';
    return 0;
}