AT_past202209_l 展覧会

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.

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 $

Print the answer.

### Sample Explanation 1 When only the $ 3 $ -rd painting is exhibited, the score is $ 3 + 5 = 8 $ points, which is maximum possible. ### Sample Explanation 2 It is optimal to exhibit no paintings. ### 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.