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>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize(3)
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("sse3", "sse2", "sse")
#pragma GCC target("avx", "sse4", "sse4.1", "sse4.2", "ssse3")
#pragma GCC target("f16c")
#pragma GCC optimize("inline", "fast-math", "unroll-loops", \
                     "no-stack-protector")
using namespace std;
const int block_size = 320;
const long long mod = 1e9 + 7;
const long long inf = 1e9 + 7;
const long double eps = 1e-9;
const double PI = atan(1) * 4;
template <typename T>
inline int sign(const T &a) {
  if (a < 0) return -1;
  if (a > 0) return 1;
  return 0;
}
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
template <typename T, typename S>
inline bool upmin(T &a, const S &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T, typename S>
inline bool upmax(T &a, const S &b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T>
inline void in(T &x) {
  x = 0;
  T f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  x *= f;
}
long long twop(int x) { return 1LL << x; }
template <typename A, typename B>
inline void in(A &x, B &y) {
  in(x);
  in(y);
}
template <typename A, typename B, typename C>
inline void in(A &x, B &y, C &z) {
  in(x);
  in(y);
  in(z);
}
template <typename A, typename B, typename C, typename D>
inline void in(A &x, B &y, C &z, D &d) {
  in(x);
  in(y);
  in(z);
  in(d);
}
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
namespace SOLVE {
long long ans;
int n, m;
const int maxn = 250010;
int pos[401];
int s[maxn], t[maxn], c[maxn], r[maxn];
int dp[401][401][401];
int tmp[402];
void main() {
  memset(dp, 0x3f, sizeof(dp));
  in(n, m);
  for (long long i = 1; i < n + 1; i++) {
    in(pos[i]);
  }
  for (long long i = 0; i < m; i++) {
    in(s[i], t[i], c[i], r[i]);
  }
  for (long long l = 1; l < n + 1; l++) {
    for (long long r = l; r < n + 1; r++) dp[l][r][0] = pos[r] - pos[l];
  }
  for (long long l = 1; l < n + 1; l++) {
    for (long long c = 0; c < n; c++) {
      memset(tmp, 0x3f, sizeof(tmp));
      int rr = l;
      for (long long r = l; r < n + 1; r++) {
        upmin(dp[l][r][c + 1], dp[l][r][c]);
        while (rr + 1 <= n and pos[rr + 1] - pos[r] <= dp[l][r][c]) {
          rr++;
          upmin(dp[l][rr][c + 1], dp[l][r][c]);
          upmin(dp[l][rr][c + 1], pos[rr] + tmp[rr]);
          upmin(tmp[rr], tmp[rr - 1]);
        }
        tmp[rr + 1] = -pos[r];
      }
    }
  }
  long long ans = 0;
  for (long long i = 0; i < m; i++) {
    upmax(ans, 1LL * c[i] * dp[s[i]][t[i]][r[i]]);
  }
  cout << ans << endl;
}
}  // namespace SOLVE
signed main() {
  int t;
  t = 1;
  while (t--) {
    SOLVE::main();
  }
  return 0;
}