from dataclasses import dataclass


def read_ints():
    return list(map(int, input().split()))


@dataclass
class Truck:
    s: int
    f: int
    c: int
    r: int


def check(trucks, M, cities):
    for truck_idx, truck in enumerate(trucks):
        remaining = truck.r
        V = M;
        rel_cities = cities[truck.s-1:truck.f]
        for city1, city2 in zip(rel_cities, rel_cities[1:]):
            needed = (city2 - city1) * truck.c
            if V >= needed:
                V -= needed
            elif remaining and M >= needed:
                V = M - needed
                remaining -= 1
            else:
                return truck_idx


n, m = read_ints()
cities = read_ints()
trucks = [Truck(*read_ints()) for _ in range(m)]

L = 0  # not possible
R = 10**18  # possible
while L + 1 < R:
    M = L + max(1, (R - L) // 2000)
    if (res := check(trucks, M, cities)) is None:
        R = M
    else:
        L = M
        trucks = trucks[res:]
print(R)