UOJ Logo Zijian Online Judge

ZOJ

#44. 梨

统计

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

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

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