심각한 사업

디마는 친구 피터가 주최하는 쇼에 참가한다. 쇼의 이름은 <>이다. 이 쇼에서 디마는 3행 n열로 이루어진 직사각형 필드 $3 \times n$을 가로질러야 한다. 각 행의 칸은 왼쪽에서 오른쪽으로 1부터 n까지 번호가 매겨져 있다.

각 칸 $(i, j)$에는 정수 $a_{i,j}$가 적혀 있다. 디마의 점수는 처음에 0이다. 디마가 $i$행 $j$열의 칸에 도달할 때마다 점수가 $a_{i,j}$만큼 변한다. 점수는 음수가 될 수 있다.

처음에는 1행과 3행의 모든 칸을 이용할 수 있고, 2행의 모든 칸은 이용할 수 없다. 특별 제안은 $q$개 있다. $i$번째 제안은 2행의 $l_i$열부터 $r_i$열까지의 칸을 이용 가능하게 만든다. 제안을 수락하면 디마의 점수가 $k_i$만큼 줄어든다. 디마는 원하는 만큼 제안을 수락할 수 있으며, 같은 칸을 여러 번 이용 가능하게 만들어도 된다.

디마는 1행 1열에서 출발해 3행 n열에 도착하려 한다. 디마는 아래 행으로 내려가거나 오른쪽 열로 이동할 수 있다. 총 $n+1$번 이동하며, 그중 가로 이동은 $n-1$번, 세로 이동은 2번이다.

피터는 디마의 최종 점수에 따라 보수를 지급한다. 최종 점수는 방문한 모든 칸의 합에서 사용한 특별 제안들의 비용을 뺀 값이다. 디마의 최종 점수가 최대가 되도록 도와라.

시간 제한은 3000 ms이고, 메모리 제한은 1024 MB이다.

첫 번째 줄에 두 정수 $n$과 $q$ ($1 \le n, q \le 500\,000$)가 주어진다. $n$은 열의 수이고, $q$는 특별 제안의 수이다.

다음 세 줄에는 필드의 값이 주어진다. $i$번째 줄에는 $a_{i,1}, a_{i,2}, \ldots, a_{i,n}$ ($-10^9 \le a_{i,j} \le 10^9$)이 주어진다.

다음 $q$줄에는 특별 제안이 주어진다. $i$번째 줄에는 정수 $l_i$, $r_i$, $k_i$ ($1 \le l_i \le r_i \le n$, $1 \le k_i \le 10^9$)가 주어진다.

디마가 얻을 수 있는 최대 최종 점수를 정수 하나로 출력한다.