Portals II

Portals II

You are standing at the first index of an array $a$ of length $n$. At index $i$, you can either take a step forward to $i+1$, or if there is a portal ($m$ portals) $x,y,z$ such that $i==x$ , you can teleport to any index in $[y,z]$. The score of a path is defined as the maximum sum of values of the indicies you visit. What is the maximum score with which you can get to index $n-1$, starting from the start of the array?

Sample Input

5 1
1 2 -100 4 5
1 2 3

Sample Output

12

Constraints

$1 \le n \le 1e5$

$1 \le m \le 1e5$

$-1e3 \le a[i] \le 1e3$

$0 \le x < y \le z < n$