Description

This is the hard version of the problem. The difference between the two versions lies in the conditions the ball must satisfy. The full score for this version is 50 points.

Renko has a small ball initially at position $0$ on the number line and moving in the positive direction. She sets up devices at points $1$ to $n$ on the number line. When the ball passes through point $i$, she can pay a cost of $a_i$ to reverse its direction (from positive to negative, or vice versa).

Renko has $m$ conditions to satisfy. The $i$-th condition states that "the ball must move from point $x_i$ to point $y_i$ at least $k_i$ times," where $x_i$ is greater than $y_i$. More precisely, this condition requires the ball's path to include segments like $\ldots \to x_i \to \ldots \to y_i \to \ldots \to x_i \to \ldots \to y_i \to \ldots$, with the movement from $x_i$ to $y_i$ repeated at least $k_i$ times.

Renko wants to determine the minimum total cost required to satisfy 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 each contain three positive integers $x_i$, $y_i$, and $k_i$.

Output Format

Output one integer: the minimum total cost required to satisfy all conditions.

3 1
1 2 3
2 1 3

8

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

8

Hint

Explanation

The figure above illustrates the movement paths for both samples. Refer to it for specific construction details.

Sample #1

Renko reverses the ball's direction when it passes point $2$, then reverses it again at point $1$. Repeating this operation twice and finally reversing at point $2$ satisfies all conditions. The total cost is $8$.

This sample satisfies Special Property A.

Sample #2

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

Constraints

Bundled testing is used.

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|c|}\hline \textbf{Subtask} & \textbf{Points} & \bm{n,m \leq} & \bm{a_i \leq} & \bm{x_i,y_i \leq} & \bm{k_i \leq} & \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 A: All $k_i$ are equal.

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

---

Translated by DeepSeek R1