Problem: There are n cities along the road, which can be represented as a straight line. The i-th city is situated at the distance of a_i kilometers from the origin. All cities are situated in the same direction from the origin. There are m trucks travelling from one city to another. 

Each truck can be described by 4 integers: starting city s_i, finishing city f_i, fuel consumption c_i and number of possible refuelings r_i. The i-th truck will spend c_i litres of fuel per one kilometer. 

When a truck arrives in some city, it can be refueled (but refueling is impossible in the middle of nowhere). The i-th truck can be refueled at most r_i times. Each refueling makes truck's gas-tank full. All trucks start with full gas-tank.

All trucks will have gas-tanks of the same size V litres. You should find minimum possible V such that all trucks can reach their destinations without refueling more times than allowed.

Input

First line contains two integers n and m (2 ≤ n ≤ 400, 1 ≤ m ≤ 250000) — the number of cities and trucks.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9, a_i < a_{i+1}) — positions of cities in the ascending order.

Next m lines contains 4 integers each. The i-th line contains integers s_i, f_i, c_i, r_i (1 ≤ s_i < f_i ≤ n, 1 ≤ c_i ≤ 10^9, 0 ≤ r_i ≤ n) — the description of the i-th truck.

Output

Print the only integer — minimum possible size of gas-tanks V such that all trucks can reach their destinations.

Example

Input


7 6
2 5 7 10 14 15 17
1 3 10 0
1 7 12 7
4 5 13 3
4 7 10 1
4 7 10 1
1 5 11 2


Output


55

Note

Let's look at queries in details: 

  1. the 1-st truck must arrive at position 7 from 2 without refuelling, so it needs gas-tank of volume at least 50. 
  2. the 2-nd truck must arrive at position 17 from 2 and can be refueled at any city (if it is on the path between starting point and ending point), so it needs gas-tank of volume at least 48. 
  3. the 3-rd truck must arrive at position 14 from 10, there is no city between, so it needs gas-tank of volume at least 52. 
  4. the 4-th truck must arrive at position 17 from 10 and can be refueled only one time: it's optimal to refuel at 5-th city (position 14) so it needs gas-tank of volume at least 40. 
  5. the 5-th truck has the same description, so it also needs gas-tank of volume at least 40. 
  6. the 6-th truck must arrive at position 14 from 2 and can be refueled two times: first time in city 2 or 3 and second time in city 4 so it needs gas-tank of volume at least 55. 

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

import static java.lang.Math.max;

public class F {

    static FastIn in;

    static boolean DO_TEST = false;
    static {
        if (DO_TEST) {
            String t1 = "7 6\n" +
                    "2 5 7 10 14 15 17\n" +
                    "1 3 10 0\n" +
                    "1 7 12 7\n" +
                    "4 5 13 3\n" +
                    "4 7 10 1\n" +
                    "4 7 10 1\n" +
                    "1 5 11 2";
            System.out.println("INPUT:");
            System.out.println(t1);
            ByteArrayInputStream byteArrayInputStream = new ByteArrayInputStream(t1.getBytes());
            in = FastIn.wrapInputStream(byteArrayInputStream);
            System.out.println("OUTPUT:");
        } else {
            in = FastIn.wrapSystemIn();
        }
    }

    public static void main(String[] args) {
        int n = in.nextInt();
        int m = in.nextInt();
        int[] a = in.nextIntArrayOfSize(n);

        int[] start = new int[m];
        int[] finish = new int[m];
        long[] cost = new long[m];
        int[] segments = new int[m];

        for (int i = 0; i < m; i++) {
            start[i] =  in.nextInt() - 1;
            finish[i] = in.nextInt() - 1;
            cost[i] = in.nextLong();
            segments[i] = in.nextInt();
        }

        ArrayList<ArrayList<Integer>> ids = new ArrayList<>(m);
        for (int i = 0; i < n; i++) {
            ids.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            ids.get(start[i]).add(i);
        }

        int[][] dp = new int[n + 1][n];


        long v = Integer.MIN_VALUE;
        for (int l = 0; l < n; l++) {
            for (int r = l; r < n; r++) {
                dp[0][r] = a[r] - a[l];
            }

            for (int k = 1; k < n + 1; k++) {
                int j = l;
                for (int r = l; r < n; r++) {
                    while (j + 1 < n && max(dp[k - 1][j], a[r] - a[j]) >= max(dp[k - 1][j + 1], a[r] - a[j + 1])) {
                        j++;
                    }
                    dp[k][r] = max(dp[k - 1][j], a[r] - a[j]);
                }
            }

            for (int id: ids.get(l)) {
                v = max(v, dp[segments[id]][finish[id]] * cost[id]);
            }
        }


       System.out.println(v);
    }



    static final class FastIn {
            private final BufferedReader bufferedReader;
            private StringTokenizer stringTokenizer;

            static FastIn wrapInputStream(InputStream inputStream) {
                return new FastIn(inputStream);
            }

            static FastIn wrapSystemIn() {
                return wrapInputStream(System.in);
            }

            private FastIn(InputStream inputStream) {
                InputStreamReader inputStreamReader = new InputStreamReader(inputStream);
                this.bufferedReader = new BufferedReader(inputStreamReader);
            }

            int nextInt() {
                return Integer.parseInt(nextToken());
            }

            long nextLong() {
                return Long.parseLong(nextToken());
            }

            String nextString() {
                return nextToken();
            }

            int[] nextIntArrayOfSize(int size) {
                int[] array = new int[size];
                for (int i = 0; i < size; i++) {
                    array[i] = nextInt();
                }
                return array;
            }

            long[] nextLongArrayOfSize(int size) {
                long[] array = new long[size];
                for (int i = 0; i < size; i++) {
                    array[i] = nextLong();
                }
                return array;
            }

            private String nextToken() {
                try {
                    skipUntilNextTokenOrEndOfStream();
                    assert hasNextToken();
                    return stringTokenizer.nextToken();
                } catch (IOException ioException) {
                    throw new RuntimeException(ioException);
                }
            }

            boolean hasNextToken() throws IOException {
                skipUntilNextTokenOrEndOfStream();
                return stringTokenizer.hasMoreTokens();
            }

            private void skipUntilNextTokenOrEndOfStream() throws IOException {
                while (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
                    String nextLine = bufferedReader.readLine();
                    if (nextLine == null) {
                        return;
                    }
                    this.stringTokenizer = new StringTokenizer(nextLine);
                }
            }
        }
}