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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
char buf[100000], *p1, *p2;
int rd() {
  int x = 0;
  char s =
      (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
           ? EOF
           : *p1++);
  while (s < '0' || s > '9')
    s = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++);
  while (s >= '0' && s <= '9')
    x = (((x << 2) + x) << 1) + s - '0',
    s = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++);
  return x;
}
namespace SA {
int n, ws[1050], wa[1050], wb[1050], rk[1050], height[1050], sa[1050];
char w[1050];
void build(int m) {
  int i, j, p, *x = wa, *y = wb;
  for (i = 1; i <= m; i++) ws[i] = 0;
  for (i = 1; i <= n; i++) ws[x[i] = w[i]]++;
  for (i = 1; i <= m; i++) ws[i] += ws[i - 1];
  for (i = n; i; i--) sa[ws[x[i]]--] = i;
  for (j = 1; j < n; j <<= 1) {
    for (p = 0, i = n; i > n - j; i--) y[++p] = i;
    for (i = 1; i <= n; i++)
      if (sa[i] > j) y[++p] = sa[i] - j;
    for (i = 1; i <= m; i++) ws[i] = 0;
    for (i = 1; i <= n; i++) ws[x[i]]++;
    for (i = 1; i <= m; i++) ws[i] += ws[i - 1];
    for (i = n; i; i--) sa[ws[x[y[i]]]--] = y[i];
    swap(x, y);
    m = 1;
    for (i = 1; i <= n; i++)
      x[sa[i]] = y[sa[i] + j] == y[sa[i + 1] + j] && y[sa[i]] == y[sa[i + 1]]
                     ? m
                     : m++;
    if (m > n) break;
  }
  for (i = 1; i <= n; i++) rk[sa[i]] = i;
  p = 0;
  for (i = 1; i <= n; i++)
    if (rk[i] != n) {
      j = rk[i] + 1;
      for (; w[i + p] == w[sa[j] + p]; p++)
        ;
      height[rk[i]] = p;
      if (p) p--;
    }
}
void init() {
  n = 6;
  w[1] = 'a';
  w[2] = 'b';
  w[3] = 'a';
  w[4] = 'b';
  w[5] = 'b';
  w[6] = 'a';
  build(128);
}
}  // namespace SA
namespace Scape_Goat_Tree {
int ch[1050][2], val[1050], siz[1050], tot[1050], ex[1050], S[1050], V[1050],
    tp, koishi;
int root, f[1050], cnt;
double AL = 0.75;
void pushup(int p) {
  siz[p] = siz[ch[p][0]] + siz[ch[p][0]] + ex[p];
  tot[p] = tot[ch[p][0]] + tot[ch[p][0]] + 1;
}
int GG(int p) { return tot[p] * AL < max(tot[ch[p][0]], tot[ch[p][0]]); }
int newnode(int v) {
  int p = ++cnt;
  siz[p] = tot[p] = ex[p] = 1;
  val[p] = v;
  return p;
}
void insert(int &p, int v, int fa) {
  if (!p) {
    p = newnode(v);
    f[p] = fa;
    return;
  }
  insert(ch[p][v > val[p]], v, p);
  pushup(p);
  if (GG(p)) koishi = p;
}
void init() {
  insert(root, 1, 0);
  insert(root, 2, 0);
  insert(root, 3, 0);
  insert(root, 4, 0);
  insert(root, 5, 0);
}
}  // namespace Scape_Goat_Tree
int l, r;
int f, c, s, t;
int n, m, a[405];
long long ans;
inline bool check(int x) {
  register int i, tc = c;
  register int now = x;
  for (i = s; i < t; i++) {
    if (a[i + 1] - a[i] > x) return 0;
    if (a[i + 1] - a[i] > now) {
      if (!tc) return 0;
      tc--;
      now = x;
    }
    now -= a[i + 1] - a[i];
  }
  return 1;
}
int V[405 * 405], lv;
int main() {
  Scape_Goat_Tree::init();
  SA::init();
  n = rd(), m = rd();
  l = 0, r = 1 << 30;
  for (int i = 1; i <= n; i++) a[i] = rd();
  int i, j;
  for (i = 1; i <= n; i++) {
    for (j = i + 1; j <= n; j++) V[++lv] = a[j] - a[i];
  }
  sort(V + 1, V + lv + 1);
  lv = unique(V + 1, V + lv + 1) - V - 1;
  while (m--) {
    s = rd();
    t = rd();
    f = rd();
    c = rd();
    if (s > t) swap(s, t);
    if (check(ans / f)) continue;
    l = 1;
    r = lv + 1;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (check(V[mid]))
        r = mid;
      else
        l = mid + 1;
    }
    ans = max((long long)V[l] * f, ans);
  }
  printf("%lld\n", ans);
}