Problem: You are a car race organizer and would like to arrange some races in Linear Kingdom.

Linear Kingdom has n consecutive roads spanning from left to right. The roads are numbered from 1 to n from left to right, thus the roads follow in the order of their numbers' increasing. There will be several races that may be held on these roads. Each race will use a consecutive subset of these roads. Also, each race will pay some amount of money to you if this race is held. No races overlap in time, so some roads can be used in several races.

Unfortunately, some of the roads are in a bad condition and they need repair. Each road has repair costs associated with it, you are required to pay this cost to repair the road. A race can only take place if all the roads used in the race are renovated. Your task is to repair such roads (possibly all or none) that will maximize your profit. Your profit is defined as the total money you get from the races that are held minus the total money you spent to repair the roads. Note that you may decide not to repair any road and gain zero profit.

Print the maximum profit you can gain.

Input

The first line contains two single-space separated integers, n and m (1 ≤ n, m ≤ 2·105), denoting the number of roads and the number of races, respectively.

Then n lines follow, each line will contain a single non-negative integer not exceeding 109 denoting the cost to repair a road. The costs are given in order from road 1 to road n.

Finally, m lines follow. Each line is single-space-separated triplets of integers. Each triplet will be given as lb, ub, and p (1 ≤ lb ≤ ub ≤ n, 1 ≤ p ≤ 109), which means that the race these three integers describe will use all the roads from lb to ub, inclusive, and if it's held you get p.

Output

Print a single integer denoting the maximum possible profit you can gain.

Please, do not use the %lld specificator to read or write 64-bit integers in C++. It is recommended to use cin, cout stream (also you may use %I64d specificator).

Examples

Input

7 4
3
2
3
2
1
2
3
1 2 5
2 3 5
3 5 3
7 7 5


Output

4


Input

2 1
0
3
1 2 5


Output

2


Input

3 1
10
10
10
1 3 10


Output

0

Note

In the first sample the optimal solution is to repair roads 1, 2, 3, and 7. Three races will take place which nets you 15. The road repair costs 11, hence your profit is 4.

Solution (in JAVA):

Solution:
import java.util.List;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.ArrayList;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author AlexFetisov
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TE solver = new TE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TE {

    public static final long NEG_INF = Long.MIN_VALUE / 2;

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int countRoads = in.nextInt();
        int countRaces = in.nextInt();
        long[] costToFix = new long[countRoads];
        for (int i = 0; i < countRoads; ++i) {
            costToFix[i] = in.nextLong();
        }
        List<Pair<Integer, Long>>[] races = new List[countRoads];
        for (int i = 0; i < countRoads; ++i) {
            races[i] = new ArrayList<Pair<Integer, Long>>();
        }

        long[] singles = new long[countRoads];

        for (int i = 0; i < countRaces; ++i) {
            int begin = in.nextInt() - 1;
            int end = in.nextInt() - 1;
            long profit = in.nextLong();
            races[end].add(Pair.makePair(begin, profit));
        }

        ISegmentTree tree = new SegmentTree(countRoads);
        long res = 0;
        long max1 = 0;
        for (int road = 0; road < countRoads; ++road) {
            if (road > 1) {
                tree.set(road, max1);
                for (Pair<Integer, Long> p : races[road]) {
                    tree.update(0, p.first, p.second);
                }
                tree.update(0, road, -costToFix[road]);
                max1 = Math.max(max1, tree.getMax(road));
            } else if (road == 0) {
                tree.set(0, 0);
                for (Pair<Integer, Long> p : races[road]) {
                    tree.update(0, p.first, p.second);
                }
                tree.update(0, road, -costToFix[road]);
                max1 = Math.max(0, tree.getMax(road));
            } else {
                tree.set(1, max1);
                for (Pair<Integer, Long> p : races[road]) {
                    tree.update(0, p.first, p.second);
                }
                tree.update(0, road, -costToFix[1]);
                max1 = Math.max(max1, Math.max(0, tree.getMax(road)));
            }
            res = Math.max(max1, res);
            res = Math.max(res, tree.getMax(road));
        }
        out.println(res);
    }

    interface ISegmentTree {
        void update(int left, int right, long value);
        long getMax(int right);
        void set(int pos, long value);
    }

    private class SegmentTree implements ISegmentTree {
        int maxTree;
        int maxRight;
        long[] max;
        long[] add;

        public SegmentTree(int size) {
            maxTree = 1;
            while (maxTree <= size) maxTree <<= 1;
            maxRight = maxTree - 1;
            maxTree <<= 1;
            max = new long[maxTree];
            Arrays.fill(max, NEG_INF);
            add = new long[maxTree];
        }

        public void update(int left, int right, long value) {
            internalAdd(1, 0, maxRight, left, right, value);
        }

        private void internalAdd(int v, int rangeLeft, int rangeRight, int left, int right, long value) {
            if (rangeLeft == left && rangeRight == right) {
                add[v] += value;
                return;
            }
            int middle = (rangeLeft + rangeRight) / 2;
            if (left <= middle) {
                internalAdd(2 * v, rangeLeft, middle, left, Math.min(right, middle), value);
            }
            if (right > middle) {
                internalAdd(2 * v + 1, middle + 1, rangeRight, Math.max(left, middle + 1), right, value);
            }
            max[v] = Math.max(max[v * 2] + add[v * 2], max[v * 2 + 1] + add[v * 2 + 1]);
        }

        private long internalGet(int v, int rangeLeft, int rangeRight, int left, int right, long value) {
            if (rangeLeft == left && rangeRight == right) {
                return max[v] + add[v] + value;
            }
            long res = NEG_INF;
            int middle = (rangeLeft + rangeRight) / 2;
            if (left <= middle)
                res = Math.max(res, internalGet(v * 2, rangeLeft, middle, left, Math.min(middle, right), value + add[v]));
            if (right > middle)
                res = Math.max(res, internalGet(v * 2 + 1, middle + 1, rangeRight, Math.max(middle + 1, left), right, value + add[v]));
            return res;
        }

        public void set(int pos, long val) {
            int rangeLeft = 0;
            int rangeRight = maxRight;
            int v = 1;

            while (rangeLeft != rangeRight) {
                int middle = (rangeLeft + rangeRight) / 2;
                max[v] += add[v];
                if (add[v] != 0) {
                    add[2 * v] += add[v];
                    add[2 * v + 1] += add[v];
                    add[v] = 0;
                }
                if (pos <= middle) {
                    rangeRight = middle;
                    v *= 2;
                } else {
                    rangeLeft = middle + 1;
                    v *= 2;
                    ++v;
                }
            }

            max[v] = val;
            add[v] = 0;
            v >>= 1;
            while (v > 0) {
                max[v] = Math.max(max[v * 2] + add[v * 2], max[v * 2 + 1] + add[v * 2 + 1]);
                add[v] = 0;
                v >>= 1;
            }
        }

        public long getMax(int right) {
            return internalGet(1, 0, maxRight, 0, right, 0);
        }
    }

}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer stt;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
    }

    public String nextLine() {
        try {
            return reader.readLine().trim();
        } catch (IOException e) {
            return null;
        }
    }

    public String nextString() {
        while (stt == null || !stt.hasMoreTokens()) {
            stt = new StringTokenizer(nextLine());
        }
        return stt.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(nextString());
    }

    public long nextLong() {
        return Long.parseLong(nextString());
    }

}

class Pair<U, V> implements Comparable<Pair<U, V>> {
    public final U first;
    public final V second;

    public static<U, V> Pair<U, V> makePair(U first, V second) {
        return new Pair<U, V>(first, second);
    }

    public Pair(U first, V second) {
        this.first = first;
        this.second = second;
    }

    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Pair pair = (Pair) o;

        return !(first != null ? !first.equals(pair.first) : pair.first != null) && !(second != null ? !second.equals(pair.second) : pair.second != null);

    }

    public int hashCode() {
        int result = first != null ? first.hashCode() : 0;
        result = 31 * result + (second != null ? second.hashCode() : 0);
        return result;
    }

    public String toString() {
        return "(" + first + "," + second + ")";
    }

    public int compareTo(Pair<U, V> o) {
        int value = ((Comparable<U>)first).compareTo(o.first);
        if (value != 0)
            return value;
        return ((Comparable<V>)second).compareTo(o.second);
    }
}