// https://szkopul.edu.pl/problemset/problem/SSCZFOeuhe8_DNgsgFo9moDz/site/?key=statement

// Przyjaciele i wrogowie

#include <bits/stdc++.h>

// using namespace std;

// #define GARY_DBG
#define GARY_LIB

#define int long long

constexpr int sizik = 500 * 1001;

#define ar std::array
#define pr std::pair
#define vec std::vector

typedef vec<vec<int>> _kra;

ar<int, sizik> a, l, r, alfa, beta;

std::bitset<sizik> delete_badboy;
int n, m;

namespace seg_tree {

int d[4 * sizik];
int lazy[4 * sizik];

void push(int v, int tl, int tr) {
    if (lazy[v] != 0 && tl != tr) {
        int addv = lazy[v];
        int left = v << 1, right = v << 1 | 1;
        d[left] += addv;
        d[right] += addv;
        lazy[left] += addv;
        lazy[right] += addv;
        lazy[v] = 0;
    } else if (tl == tr) {
        lazy[v] = 0;
    }
}

void update(int v, int tl, int tr, int l, int r, int val) {
    if (l > r) return;
    if (l == tl && r == tr) {
        d[v] += val;
        lazy[v] += val;
    } else {
        push(v, tl, tr);
        int tm = (tl + tr) >> 1;
        if (r <= tm)
            update(v << 1, tl, tm, l, r, val);
        else if (l > tm)
            update(v << 1 | 1, tm + 1, tr, l, r, val);
        else {
            update(v << 1, tl, tm, l, tm, val);
            update(v << 1 | 1, tm + 1, tr, tm + 1, r, val);
        }
        d[v] = std::max(d[v << 1], d[v << 1 | 1]);
    }
}

int query(int v, int tl, int tr, int l, int r) {
    if (l > r) return INT64_MIN;
    if (l == tl && r == tr) {
        return d[v];
    }
    push(v, tl, tr);
    int tm = (tl + tr) >> 1;
    if (r <= tm)
        return query(v << 1, tl, tm, l, r);
    else if (l > tm)
        return query(v << 1 | 1, tm + 1, tr, l, r);
    else
        return std::max(query(v << 1, tl, tm, l, tm), query(v << 1 | 1, tm + 1, tr, tm + 1, r));
}

void add(int l, int r, int delta) {
    if (l < 1) l = 1;
    if (r > n + 2) r = n + 2;
    if (l > r) return;
    update(1, 1, n + 2, l, r, delta);
}

int get_max(int l, int r) {
    if (l < 1) l = 1;
    if (r > n + 2) r = n + 2;
    if (l > r) return INT64_MIN;
    return query(1, 1, n + 2, l, r);
}

}

bool is_in(int x, int y, int z, int q) {
    assert(x <= y && z <= q);
    // z -> x -> y -> q
    return z <= x && y <= q;
}

struct Event {
    bool d;
    int x, y;
    int w;
    int k;

    Event(bool d1, int x1, int y1, int w1, int k1) : d(d1), x(x1), y(y1), w(w1), k(k1) {}
};

std::vector<Event> events;

void solve() {
    std::cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        l[i] = r[i] = i;
        alfa[i] = 0;
        beta[i] = n + 1;
    }

    for (int i = 1; i <= m; i++) {
        int t, x, y;
        std::cin >> t >> x >> y;
        if (x == y) continue;

        if (t == 1) {
            if (y > x) {
                r[x] = std::max(r[x], y);
            } else {
                l[x] = std::min(l[x], y);
            }
        } else {
            assert(t == 2);
            if (y > x) {
                beta[x] = std::min(beta[x], y);
            } else {
                alfa[x] = std::max(alfa[x], y);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (!is_in(l[i], r[i], alfa[i], beta[i])) {
            delete_badboy[i] = true;
        } else {
            events.push_back({0, alfa[i], l[i] - 1, a[i], r[i]});
            events.push_back({1, alfa[i], l[i] - 1, a[i], beta[i]});
        }
    }

    std::sort(events.begin(), events.end(), [](const Event& x, const Event& y) {
        if (x.k == y.k) return x.d < y.d;
        return x.k < y.k;
    });

    int idx = 0;
    const int NN = (int)events.size();

    // licz dp
    for (int i = 2; i <= n + 1; i++) {
        while (idx < NN && (events[idx].k == (i - 1))) {
            if (events[idx].d == 0) {
                seg_tree::add(events[idx].x + 1, events[idx].y + 1, events[idx].w);
            } else {
                seg_tree::add(events[idx].x + 1, events[idx].y + 1, -events[idx].w);
            }
            idx++;
        }

        int wyn = std::max(seg_tree::get_max(1, i - 1), 0ll);
        seg_tree::add(i, i, wyn);
    }

    int ans = seg_tree::get_max(n + 1, n + 1);
    std::cout << ans << std::endl;
}

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}