Description

APIO 就要开始了，尽管需要准备转系考试，XHL 被北大抓去负责中国赛区比赛的筹备。

XHL 刚上任就遇到了一个难题 : 为 APIO 招募一批短期志愿者。

APIO 比赛持续 $N$ 天，其中第 $i$ 天至少需要 $A_i$ 个人。

XHL 通过了解得知，一共有 $M$ 类志愿者可以招募。每类志愿者可以工作的时间是连续的几段，其中第 $i$ 段可以从 $S_i$ 天工作到 $T_i$ 天。不过，由于志愿者都是妹子，XHL 招募志愿者是需要损耗自己的魅力值的，对于第 $i$ 类志愿者，每人需要消耗 $C_i$ 的魅力值（我才没在吐槽“奥运志愿者”居然是收费的！！）。为了让自己以后依然能泡到更多的妹子，XHL 希望用尽量少的魅力值招募足够的志愿者。尽管泡妹子是他的特长，但是计算最小值这种问题他已经不干很多年了！所以 XHL 找到了你，希望你帮他设计一种最优的招募方案。

Input Format

第一行包含两个整数 $N,M$ ，表示完成 APIO 的天数和可以招募的志愿者的种类。

接下来的一行包含 $N$ 个非负整数，表示每天至少需要的志愿者人数。

接下来的 $M$ 行中，每行第一个数是 $k$ ，表示每类志愿者工作的段数。接下来 $2k$ 个整数，每两个数 $S_i,T_i$ 表示每一段的起止时间。这一行的最后一个整数是 $C_i$，表示这类志愿者每个所消耗的魅力值。为了方便起见，我们可以认为每类志愿者的数量都是无限多的。

Output Format

仅包含一个整数，表示你所设计的最优方案的总魅力值损耗。

3 3
2 3 4
1 1 2 2
1 2 3 5
1 3 3 2

14

Hint

$100\%$ 的数据中，$1\le N\le 1000, 1\le M\le 10000$ ，其他数据保证合法且小于 $10^9$ 。