题目描述

在一条由西向东的公路上有 $n$ 个路口，编号从 $1$ 到 $n$，第 $i$ 个路口距离公路的起点 $a_i$ 公里。每个路口都有一个加油站。有 $m$ 辆卡车将要在这条公路上行驶。

每一辆卡车都可以用 $4$ 个整数来表示：起点 $s_i$，终点 $f_i$，每公里耗油量 $c_i$，以及最多可以加油的次数 $r_i$。也就是说，对于第 $i$ 辆卡车，它需要从第 $s_i$ 个路口行驶到第 $f_i$ 个路口，它每行驶一公里要消耗 $c_i$ 升汽油，它可以在中间经过的加油站中选择最多 $r_i$ 个加油站加油。在经过的路口加油都会让卡车的邮箱加满。卡车在出发的时候油箱是满的。

你需要为所有的卡车设计一款公用容量为 $V$ 升的油箱，使每一辆卡车都能在满足上述条件的情况下行驶完它们对应的行程。求这个最小的 $V$。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$，以一个空格分隔，分别表示路口和卡车的数量（$2 \le n \le 400, 1 \le m \le 250000$）。

输入的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n(1 \le a_i \le 10^9, a_i \lt a_{i+1})$，两两之间以一个空格分隔，表示每一个路口距离公路起点的公里数。

接下来 $m$ 行，每行包含 $4$ 个整数。其中第 $i$ 行包含 $4$ 个整数 $s_i, f_i, c_i, r_i(1 \le s_i \lt f_i \le n, 1 \le c_i \le 10^9, 0 \le r_i \le n)$，表示第 $i$ 辆卡车的相关信息（具体见题目描述）。

输出格式

输出一个整数，表示最小的满足条件的油箱容量 $V$ 。

样例

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

55

样例解释

1. 第 $1$ 辆卡车（$2 \rightarrow 7$）中途不加油，至少需要 $50$ 升汽油；
2. 第 $2$ 辆卡车（$2 \rightarrow 17$）可以选择在途中的每个路口都加一次油，至少需要 $48$ 升汽油；
3. 第 $3$ 辆卡车（$10 \rightarrow 14$）中途没有路口，至少需要 $52$ 升汽油；
4. 第 $4$ 辆卡车（$10 \rightarrow 17$）可以选择在第 $5$ 个路口加油（对应位置 $14$），至少需要 $40$ 升汽油；
5. 第 $5$ 辆卡车（$10 \rightarrow 17$）和第 $4$ 辆卡车的信息完全相同，所以其也至少需要 $40$ 升汽油；
6. 第 $6$ 辆卡车（$2 \rightarrow 15$）可以加两次汽油，第一次可以选择第 $2$ 或 $3$ 个路口，第二次选择第 $4$ 路口，至少需要 $55$ 升汽油。

数据范围

• 对于 $10\%$ 的数据，保证 $n,m \le 10$；
• 对于 $20\%$ 的数据，保证 $n \le 100, m \le 1000$；
• 对于 $40\%$ 的数据，保证 $n \le 400, m \le 10000$；
• 对于 $100\%$ 的数据，保证 $2 \le n \le 400, 1 \le m \le 250000, 1 \le a_i \le 10^9, a_i \lt a_{i+1}, 1 \le s_i \lt f_i \le n, 1 \le c_i \le 10^9, 0 \le r_i \le n$。