You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

人心激动。天主仿佛降临在狭窄的哥特式街头，信徒们小心在意地到处挂起彩幔，地上铺满金沙。

Description

天主降临，留下了一个长度为$n$的整数序列$A$

信徒挂起$m$块彩幔，第$i$块上写了三个数字$(B_i,C_i,D_i)$

若第$i$块彩幔随风飘起，序列$A$会发生一些变化，$A_{B_i} :=A_{B_i}+D_i,A_{C_i} :=A_{C_i}-D_i$

果壳大神甫^正在指挥迎接圣体的队伍，^可以指定每块彩幔的悬挂方式，使之随风飘起或在风中巍然不动

神甫告诉信徒，序列的子段和是这样定义的：

$$A_{[L,R]}=\sum_{i=L}^{R}A_i$$

神谕又云，序列$A$的虔诚值定义如下

$$Value(A)=\max_{1\le L\le R\le n}{|A_{[L,R]}|}$$

神甫需要合理地指挥迎圣体的队伍悬挂彩幔，使得序列$A$的虔诚值达到最大

唯有如此，才能通过天主的考验，方能让圣体安然抵达

请你帮助神甫^解决这个问题，求解最大的可能的虔诚值

Format

Input

第一行，包含两个正整数$n,m$，即序列的长度和彩幔的数量

第二行，$n$个整数，表示序列$A$的初始值

接下来$m$行，每行三个整数$B_i,C_i,D_i$，描述一块彩幔

Output

一行，一个整数，表示最大的可能的虔诚值

Samples

4 4
4 -10 6 7
1 3 -2
3 4 2
2 4 2
3 4 -5

15

Sample Explanation

神甫指挥迎圣体的队伍固定彩幔使得第一块随风飘起，其余巍然不动，此时天主序列$A$变为$2,-10,8,7$，虔诚值为

$$Value(A)=\max_{1\le L\le R\le n}{|A_{[L,R]}|}=|A_{[3,4]}|=15$$

取到最大值。

Limitation

$1\le n,m \le 2\times 10^5;$

$1\le B_i < C_i\leq n;$

$-10^8\le A_i, D_i\le 10^8$