分数: 6 点
问题陈述
有 N 画作编号 1, \dots, N。 我们将选择其中一些在展览中展示。
评论家高桥决定对展览的评分如下:
- 对于 i = 1, \dots, N,添加 A_i 点如果绘画 展出 i 。
- 此外,对于
如果满足以下所有条件,则 j = 1 \dots, M,添加 P_j 点:
- 带有指数的展出画作数量 严格小于 Q_j 等于 L_j 模数 3.
- 带有指数的展出画作数量 大于或等于 Q_j 等于 R_j 模数 3.
打印展览的最大可能分数。
约束
- 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)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
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 2 1 2 3 4 3 2 0 5 2 0 1
示例输出 1
8
当仅 3-第一幅作品展出,评分为 3 + 5 = 8 点,这是最大可能的点。
示例输入 2
1 1 1 10 1 0 0
示例输出 2
10
最好不要展出任何绘画作品。
示例输入 3
4 1 3 1 4 1 5 3 1 1
示例输出 3
12