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 ~