Background

Lian Zi is conducting research on the physical properties of objects to refine her thesis. Due to the overwhelming amount of work, she invites you to help with a small experiment, which is slightly more challenging this time.

Problem Description

This is the hard version of the problem, where the conditions the ball needs to meet are different from the easy version. The full score for this problem is 50 points.

Lian Zi has a ball that starts at point $0$ on a number line and moves in the positive direction. She has set up devices at points $1$ to $n$ on the number line. When the ball passes point $i$, she can spend $a_i$ cost to change its direction (from positive to negative or vice versa).

Lian Zi has $m$ conditions to meet, where the $i$-th condition is that the ball must move from point $x_i$ to point $y_i$ at least $k_i$ times, with $x_i$ greater than $y_i$. More specifically, this condition requires the ball's path to be like $\ldots\to x_i\to\ldots\to y_i\to\ldots\to x_i\to\ldots\to y_i\to\ldots$, with the process of moving from $x_i$ to $y_i$ repeated at least $k_i$ times.

Lian Zi wants to know the minimum cost required to meet all conditions.

Input Format

The first line contains two integers $n$ and $m$.

The second line contains $n$ positive integers describing the sequence $a$.

The next $m$ lines, the $i$-th line contains three positive integers representing $x_i$, $y_i$, and $k_i$.

Output Format

A single integer on one line, representing the minimum cost Lian Zi needs to spend to meet all conditions.

Sample Input and Output

Input Sample #1

3 1
1 2 3
2 1 3

Output Sample #1

8

Input Sample #2

5 3
5 2 3 4 5
2 1 1
3 2 2
3 1 1

Output Sample #2

8

Notes

Sample Explanation

The above diagram illustrates the specific construction schemes for Sample 1 and Sample 2, for reference.

Sample #1

Lian Zi reverses the ball's direction when it passes point $2$, then reverses it again when it passes point $1$. She repeats this operation twice, and finally reverses the direction at point $2$ to meet all conditions. The total cost is $8$.

Note that this sample satisfies the special property $\mathbf{A}$.

Sample #2

Lian Zi reverses the ball's direction sequentially at points $3$, $2$, and $3$. The total cost is $8$.

Data Range

This problem uses subtask testing.

$$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|c|}\hline \textbf{Subtask} & \textbf{Points} & n,m\le & a_i\le & x_i,y_i\le & k_i\le & \textbf{Special Property} & \textbf{Subtask Dependencies} \cr\hline 1 & 10 & 10 & 100 & 10 & 10 & - &-\cr\hline 2 & 5 & 2\times 10^5 & 10^8 & 2\times 10^5 & 10^8 & \mathbf{A}&- \cr\hline 3 & 15 & 10^3 & 10^8 & 10^3 & 10^5 & -&1 \cr\hline 4 & 20 & 2\times 10^5 & 10^8 & 2\times 10^5 & 10^8 & -&1,2,3 \cr\hline \end{array} $$

Special Property $\mathbf{A}$: All $k_i$ are equal.

For all data, the following holds: $1\le n,m\le 2\times 10^5$, $1\le a_i\le 10^8$, $1\le y_i< x_i \le n\le 2\times 10^5$, $1\le k_i\le 10^8$.

见题面 Input 部分

见题面 Output 部分