406111: GYM102268 D Dates

Ilya loves dating! He is planning his dates for the next $$$t$$$ days (these days are numbered from $$$1$$$ to $$$t$$$). For each day $$$x$$$, he knows that 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 will get $$$p_i$$$ pleasure for dating this girl. For each $$$i < n$$$, it is true that $$$l_i \leq l_{i+1}$$$ and $$$r_i \leq r_{i+1}$$$.

Ilya's goal is to plan dates with some girls to maximize total pleasure. Help him! Find the maximum total pleasure he can get if he will properly choose the girls and the days of dates with them.

The first line contains two integers $$$n$$$ and $$$t$$$: the number of girls and the number of days ($$$1 \leq n, t \leq 300\,000$$$).

The next line contains $$$t$$$ integers $$$a_1, a_2, \ldots, a_t$$$: here, $$$a_i$$$ is the maximum number of dates Ilya can plan on day $$$i$$$ ($$$0 \leq a_i \leq n$$$).

The next $$$n$$$ lines contain the descriptions of the girls. The $$$i$$$-th of these lines contains three integers, $$$l_i$$$, $$$r_i$$$, and $$$p_i$$$: the borders of the $$$i$$$-th girl's days segment and the pleasure Ilya will get for dating her ($$$1 \leq l_i \leq r_i \leq t$$$, $$$1 \leq p_i \leq 10^9$$$).

It is guaranteed that, for each $$$i < n$$$, it is true that $$$l_i \leq l_{i+1}$$$ and $$$r_i \leq r_{i+1}$$$.

Print one integer: the maximum total pleasure Ilya can get if he will properly choose the girls and the days of dates with them.

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

7