← 返回题目列表

AtCoder · past202209_l

L. 展览

中文机器翻译题面 查看原题

分数: 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