物理实验 (hard)

**这是该题的困难版本，两个版本之间的区别在于小球需要满足的条件不同。该题的满分为 50 分。** 莲子有一个初始在数轴 $0$ 点并向数轴正方向移动的小球。莲子在数轴的 $1$ 到 $n$ 这 $n$ 个点上设置了装置，当小球经过点 $i$ 时，她可以花费 $a_i$ 的代价让其改变移动方向（从数轴正方向切换为负方向，或者相反）。 莲子有 $m$ 个需要满足的条件，第 $i$ 个条件形如“小球需要从点 $x_i$ 移动到点 $y_i$ 至少 $k_i$ 次”，**其中** $x_i$ **大于** $y_i$。更详细的说，该条件即要求小球的移动路径形如 $\ldots\to x_i\to\ldots\to y_i\to\ldots\to x_i\to\ldots\to y_i\to\ldots$，其中从 $x_i$ 移动到 $y_i$ 的过程重复至少 $k_i$ 次。 莲子想要知道她至少要花费多少代价才能满足所有条件。 ## Input 第一行两个整数 $n,m$。 第二行 $n$ 个正整数描述序列 $a$。 接下来 $m$ 行中，第 $i$ 行依次给出三个正整数表示 $x_i$, $y_i$ 和 $k_i$。 ## Output 一行一个整数，表示莲子至少要花费多少代价才能满足所有条件。 [samples] ## Background 莲子为了完善她的论文，决定研究一些物体的物理性质。由于工作实在是太多，她邀请你帮忙完成其中的一个小实验。不过，这次的略微困难一些。 ## Note ### 样例解释  上图画出了样例 1 和样例 2 的具体构造方案，可供参考。 #### 样例 \#1 莲子让小球在经过点 $2$ 时反转方向，然后让其经过点 $1$ 时再反转方向。重复上述操作两次，最后再在点 $2$ 反转方向恰好能满足所有条件。总花费代价为 $8$。 注意到该样例符合特殊性质 $\mathbf{A}$。 #### 样例 \#2 莲子让小球依次在经过点 $3$、点 $2$、点 $3$ 时反转方向。总花费代价为 $8$。 ### 数据范围 **本题采用捆绑测试。** $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|c|}\hline \textbf{Subtask} & \textbf{\textsf{分值}} & \bm{n,m\le } & \bm{a_i\le} & \bm{x_i,y_i\le} & \bm{k_i\le} & \textbf{\textsf{特殊性质}}&\textbf{Subtask \textsf{依赖}}\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} $$ 特殊性质 $\mathbf{A}$：所有的 $k_i$ 均相等。 对于所有数据满足：$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$。