AT_past202209_l 展覧会

有 $N$ 幅画作，编号为 $1, \dots, N$。我们要从中选择若干幅进行展览。 评论家高桥先生对展览的评分规则如下： - 对于 $i = 1, \dots, N$，如果第 $i$ 幅画展出，则得 $A_i$ 分。 - 另外，对于 $j = 1, \dots, M$，如果以下所有条件都满足，再得 $P_j$ 分： - 展出编号**严格小于** $Q_j$ 的画作的数量对 $3$ 取模后等于 $L_j$。 - 展出编号**大于等于** $Q_j$ 的画作的数量对 $3$ 取模后等于 $R_j$。 请输出展览可能获得的最高分数。

输入通过标准输入给出，格式如下： > $N$ $M$ $A_1$ $\ldots$ $A_N$ > $P_1$ $Q_1$ $L_1$ $R_1$ > $\vdots$ > $P_M$ $Q_M$ $L_M$ $R_M$

输出答案。

### 样例解释 1 当且仅当展出第 $3$ 幅画作时，所得分数为 $3 + 5 = 8$ 分，为可以达到的最大值。 ### 样例解释 2 最优的方案是不展出任何画作。 ### 约束条件 - $1 \leq N, M \leq 2 \times 10^5$ - $1 \leq A_i \leq 10^9 \; (1 \leq i \leq N)$ - $1 \leq P_j \leq 10^9 \; (1 \leq j \leq M)$ - $1 \leq Q_j \leq N + 1 \; (1 \leq j \leq M)$ - $0 \leq L_j, R_j \leq 2 \; (1 \leq j \leq M)$ - 输入中的所有值均为整数。 由 ChatGPT 5 翻译