Dates

Ilya loves dating. He plans dates for the next $t$ days, numbered from 1 to $t$. For each day $x$, he can plan at most $a_x$ dates.

Ilya has $n$ known girls, numbered from 1 to $n$. Girl $i$ is willing to go on a date with him at most once, on any day in $[l_i, r_i]$, and Ilya gets $p_i$ pleasure for dating her. For every $i < n$, $l_i \le l_{i+1}$ and $r_i \le r_{i+1}$.

Ilya wants to choose some of the girls and the days of their dates to maximize the total pleasure.

The first line contains two integers $n$ and $t$ ($1 \le n, t \le 300000$). The next line contains $t$ integers $a_1, a_2, \ldots, a_t$ ($0 \le a_i \le n$). The next $n$ lines each contain three integers $l_i$, $r_i$, and $p_i$ ($1 \le l_i \le r_i \le t$, $1 \le p_i \le 10^9$).

Print one integer: the maximum total pleasure Ilya can get.