梨富含丰富的维生素，可以说是一种非常养生的水果了。
名侦探江户川柯南，它是如何做到长生不老，到哪哪有人的生命被夺走的呢？秘诀就是他每天都会喝雪梨枸杞汤。然而很久以来给他批发雪梨的供应商也不幸去世了，他只好凑活在流动商贩那里购买零售的雪梨。
江户川柯南需要规划接下来的 $n$ 天的雪梨供应，第 $i$ 天他需要 $a_i$ 颗雪梨来养生。
柯南在探案的旅途中会遇到 $m$ 名商贩，第 $i$ 名商贩是在 $t_i$ 天遇到的，他总共可以售卖 $b_i$ 颗梨，而且梨可能不太新鲜，总共放 $k_i$ 天就会坏掉，即柯南如果买了就只能在第 $t_i$ 至 $t_i + k_i - 1$ 天食用它。
请你规划他的购买方案，使得总花费最小。
输入格式
第一行两个正整数 $n, m$ ，表示天数和商贩数。
第二行 $n$ 个正整数 $a_i$ 。
接下来 $m$ 行每行两个整数 $b_i, c_i, t_i, k_i$，分别表示售卖上限，售卖单价，售卖时间和新鲜程度。
输出格式
如果可以规划，输出最小费用。
如果无解，输出 $-1$ 。
样例 1
input
3 3
3 5 4
6 1 1 3
3 10 1 2
4 3 2 2output
38限制与约束
$1 \le n \le 1000$, $1 \le m \le 2000$, $1 \le a_i, b_i, c_i \le 1000$, $1 \le t_i, k_i, t_i + k_i - 1 \le n$
Subtask 1 (45 pts.)，$1 \le n \le 50, 1 \le m \le 100$
Subtask 2 (55 pts.)，$1 \le n \le 1000, 1 \le m \le 2000$
时间限制：$3\,\mathrm{s}$
空间限制：$256\,\mathrm{MB}$