AT_kupc2019_f カズマ王国の陥落

在卡兹玛王国中，有 $N$ 个城镇，每个城镇中住着一位勇者。 第 $i(1≤i≤N)$ 城镇中的勇者最多可以击败 $A_i$ 只怪兽。勇者们渴望获得经验值，因此会尽可能多地击败前来自己城镇的怪兽。 你是魔王，在统治下有 $M$ 个据点。第 $j(1 ≤ j ≤ M)$ 个据点可以自由地派遣 $B_j$ 只怪兽到第 $L_j, L_j+1, ...,R_j-1, R_j$ 个城镇。未被勇者击败的怪兽数量将给予卡兹玛王国造成伤害。 请计算卡兹玛王国所受到的最大总伤害。

第一行，有一个数 $N$ 表示城镇个数。 第二行，有 $N$ 个整数 $A_1,A_2,...,A_n$ 表示每个城镇中的勇者最多可以击败的怪兽个数。 第三行，有一个整数 $M$ 表示据点个数。 接下来的 $M$ 行，第 $j$ 行有三个整数 $L_j,R_j,B_j$，描述了第 $j$ 个据点的 $L,R,B$。

请输出卡兹玛王国所受到的最大总伤害。

- 输入均为整数。 - $ 1 \leq N \leq 3000 $ - $ 1 \leq M \leq 3000 $ - $ 1 \leq A_i \leq 10^9 $ - $ 1 \leq B_j \leq 10^9 $ - $ 1 \leq L_j \leq R_j \leq N $ #### 样例解释 1 如果按照以下方式派遣，可以给卡兹玛王国造成总共 $7$ 点伤害： - 从第 $1$ 个据点派遣 $5$ 只怪兽到第 $2$ 个城镇，$2$ 只怪兽到第 $3$ 个城镇。 - 从第 $2$ 个据点派遣 $4$ 只怪兽到第 $2$ 个城镇。 - 从第$3$ 个据点各派遣 $3$ 只怪兽到第 $3$ 个城镇。 #### 样例解释 4 请注意防止溢出。