梨富含豐富的維生素，可以說是一種非常養生的水果了。

名偵探江戶川柯南，它是如何做到長生不老，到哪哪有人的生命被奪走的呢？秘訣就是他每天都會喝雪梨枸杞湯。然而很久以來給他批發雪梨的供應商也不幸去世了，他只好湊合在流動商販那裡購買零售的雪梨。

江戶川柯南需要規劃接下來的 $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

3 3
3 5 4
6 1 1 3
3 10 1 2
4 3 2 2

輸出格式 1

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$

子任務 1 (45 pts.)，$1 \le n \le 50, 1 \le m \le 100$

子任務 2 (55 pts.)，$1 \le n \le 1000, 1 \le m \le 2000$