梨富含丰富的维生素，可以说是一种非常养生的水果了。

名侦探江户川柯南，它是如何做到长生不老，到哪哪有人的生命被夺走的呢？秘诀就是他每天都会喝雪梨枸杞汤。然而很久以来给他批发雪梨的供应商也不幸去世了，他只好凑活在流动商贩那里购买零售的雪梨。

江户川柯南需要规划接下来的 $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 2

output

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}$