L - Exhibition Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

問題文

1, \dots, N と番号付けられた N 枚の絵画があります。展覧会を開いて、これらの絵画のうちいくつかを展示することになりました。

美術評論家の高橋君は、展覧会のおすすめ度を以下に示すように点数化することにしました。

  • i = 1, \dots, N について、絵画 i が展示されているなら A_i 点を加算する。
  • さらに、j = 1 \dots, M について、以下の条件が全て満たされるとき P_j 点を加算する。
    • 展示されている絵画のうち番号が Q_j 未満のものの個数を 3 で割った余りが L_j に等しい。
    • 展示されている絵画のうち番号が Q_j 以上のものの個数を 3 で割った余りが R_j に等しい。

展覧会のおすすめ度の点数としてありうる最大値を求めてください。

制約

  • 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

Score : 6 points

Problem Statement

There are N paintings numbered 1, \dots, N. We are going to choose some of them to display in an exhibition.

Takahashi the critic has decided to score the exhibition as follows:

  • For i = 1, \dots, N, add A_i points if Painting i is exhibited.
  • Additionally, for j = 1 \dots, M, add P_j points if all of the following conditions are satisfied:
    • The number of exhibited paintings with indices strictly less than Q_j is congruent to L_j modulo 3.
    • The number of exhibited paintings with indices greater than or equal to Q_j is congruent to R_j modulo 3.

Print the maximum possible score of the exhibition.

Constraints

  • 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)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 \ldots A_N
P_1 Q_1 L_1 R_1
\vdots
P_M Q_M L_M R_M

Output

Print the answer.

Sample Input 1

3 2
1 2 3
4 3 2 0
5 2 0 1

Sample Output 1

8

When only the 3-rd painting is exhibited, the score is 3 + 5 = 8 points, which is maximum possible.

Sample Input 2

1 1
1
10 1 0 0

Sample Output 2

10

It is optimal to exhibit no paintings.

Sample Input 3

4 1
3 1 4 1
5 3 1 1

Sample Output 3

12