AT_past202209_l 展覧会

$ 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 $ に等しい。 展覧会のおすすめ度の点数としてありうる最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ \ldots $ $ A_N $ $ P_1 $ $ Q_1 $ $ L_1 $ $ R_1 $ $ \vdots $ $ P_M $ $ Q_M $ $ L_M $ $ R_M $

答えを出力せよ。

### Sample Explanation 1 $ 3 $ 番目の絵のみを展示するとき、おすすめ度は $ 3 + 5 = 8 $ 点となり、これが最大です。 ### Sample Explanation 2 一枚も絵を展示しないのが最適です。 ### 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) $ - 入力は全て整数