P7867 "EVOI-RD1" Circus.

WuuTue owns a circus. The circus goes on tour around the country, and recently WuuTue's circus arrived in City T.

City T has a special performance street. The street is a straight road running from west to east, and there are $n$ stages on the street from west to east, numbered $1, 2, \dots, n$. WuuTue plans to hold $m$ performances on the performance street in City T. The $i$-th performance occupies a consecutive range of stages from $l_i$ to $r_i$ (including $l_i$ and $r_i$). At the same time, WuuTue knows that the $i$-th performance will earn $v_i$ yuan. Since the stages on the performance street are designed for human performances, if they are to be used for animal performances, they need to be reinforced. Reinforcing the $i$-th stage costs $c_i$ yuan, and it only needs to be done once and can be reused. That is, if multiple performances use stage $i$, the reinforcement cost only needs to be paid once. Of course, if WuuTue finds that a performance may not be profitable due to high reinforcement costs, they may cancel that performance. Because WuuTue is too weak, please help WuuTue calculate the maximum amount of money they can earn.

The first line: two space-separated integers $n$ and $m$, representing the number of stages and the number of performances. Lines $2$ to $n+1$: each line contains $1$ integer. The integer on line $i+1$ is the cost $c_i$ to reinforce stage $i$. Lines $n+2$ to $n+m+1$: each line contains $3$ space-separated integers. The $3$ integers $l_i$, $r_i$, $v_i$ on line $n+i+1$ indicate that the $i$-th performance needs to occupy consecutive stages from $l_i$ to $r_i$, and it can earn $v_i$ yuan.

One line: one integer, representing the maximum profit WuuTue can obtain.

**This problem uses bundled testdata.** For $20\%$ of the testdata, $1 \le n , m \le 100$. For another $20\%$ of the testdata, $v_i = c_i = 1$. For another $20\%$ of the testdata, $l_i = r_i$. For $100\%$ of the testdata, $1 \le n , m \le 10^6 , 0 \le v_i , c_i \le 10^9 , 1 \le l_i \le r_i \le n$。 Translated by ChatGPT 5