K. Hyperscale AI Data Center
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are an intern at a hyperscale AI data center that manages a linear array of $$$n$$$ GPUs. The $$$i$$$-th GPU currently runs a compute load of $$$a_i$$$.

The data center hosts workloads for $$$m$$$ different companies. Each company $$$j$$$ uses a contiguous range of GPUs from index $$$L_j$$$ to $$$R_j$$$. Different companies may share some GPUs if their computations are colocated for efficiency, so these ranges can overlap.

Before a major demonstration, the management team sets strict balance requirements. For each company $$$j$$$, the total effective compute load across its range must lie between $$$A_j$$$ and $$$B_j$$$ inclusive.

You are allowed to adjust the load of each GPU by applying an integer change $$$\Delta_i$$$. Each adjustment can either increase or decrease the load, but all must stay within a non-negative common safety limit $$$k$$$, meaning every GPU's load can change by at most $$$k$$$ units. The smaller the limit, the better the system stability, so you aim to meet all company requirements using the smallest possible $$$k$$$.

Additionally, for hardware stability, each GPU must remain above the minimal safe operating load after adjustment: $$$a_i + \Delta_i \ge 1$$$ for all $$$i$$$.

Find the minimum integer $$$k$$$ such that there exist integer adjustments $$$\Delta_1, \Delta_2, \ldots, \Delta_n$$$ satisfying, for every company $$$j$$$,

$$$$$$ A_j \le (a_{L_j} + \Delta_{L_j}) + (a_{L_j+1} + \Delta_{L_j+1}) + \dots + (a_{R_j} + \Delta_{R_j}) \le B_j. $$$$$$

If this is impossible for any $$$k$$$, output -1.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \le n, m \le 1 \cdot 10^3)$$$ — the number of GPUs and the number of companies.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — the current compute loads of the GPUs.

Each of the following $$$m$$$ lines describes one company and contains four integers $$$L_j$$$, $$$R_j$$$, $$$A_j$$$, and $$$B_j$$$ $$$(1 \le L_j \le R_j \le n,\; 1 \le A_j \le B_j \le 10^{12})$$$, meaning the $$$j$$$-th company uses all GPUs from index $$$L_j$$$ to $$$R_j$$$ and its total load must lie between $$$A_j$$$ and $$$B_j$$$ inclusive.

Output

Print a single integer: the minimal possible $$$k$$$ such that there exist integer adjustments meeting all company conditions, the per-GPU safety floor $$$a_i + \Delta_i \ge 1$$$, and $$$|\Delta_i| \le k$$$ for all GPUs. If no such $$$k$$$ exists, print $$$-1$$$.

Example
Input
5 3
2 8 5 7 4
1 3 15 20
2 5 16 20
4 4 6 6
Output
2
Note

For the sample test, $$$k = 0$$$ or $$$k = 1$$$ are not feasible. For $$$k = 2$$$, possible final compute load distributions include $$$[4, 7, 4, 6, 3]$$$ or $$$[3, 8, 4, 6, 2]$$$.