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 翻译